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\).
