Equivalence by isomorphism

Task number: 3598

Show that isomorphism yields an equivalence relation on a graph with \(V_G=\{1,…,n\}\).

Determine which graphs have equivalence classes with the greatest number of elements and find an example of such a graph for appropriate \(n\).

  • Solution

    The relation of "being" ismorphic is

    • reflexive – every graph is isomorphic to itself via the identity permutation
    • symmetric – if \(f: G\to H\) is an isomorphism, then the mapping \(f^{-1}: H\to G\) is also an isomorphism (every bijection has an inverse mapping, and preserving edges and non-edges in \(f\) leads to preserving edges and non-edges in \(f^{-1}\))
    • transitive – if \(f: F\to G\) and \(g: G\to H\) are isomorphisms, then their composition \(g\circ f\) is a bijection that preserves edges and non-edges and so is an isomorphism.

      (Formally \((u,v)\in E_F \Leftrightarrow (f(u),f(v))\in E_G \Leftrightarrow (g(f(u)),g(f(v)))=((g\circ f)(u),(g\circ f)(v))\in E_H\).)

    The largest number of isomorphic graphs, concretely \(n!\), on the set \(\{1,…,n\}\) are found from asymmetric graphs, because every renumbering of vertices gives a different graph.

    An example of an asymmetric graph for \(n\ge 6\) is \(P_n\cup\{(2{,}4)\}\), i.e. a path on vertices, where the second and fourth vertices are joined by an edge.

    1 must map to itself, because it is the only vertex with degree one neighboring a vertex with degree three, thanks to which 2 must map to itself, 4 must also map to itself, because there is no other remaining vertex of degree three, etc.

    By analyzing cases we may determine that with at most five vertices there are no asymmetric graphs with the exception of \(K_1\).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email