-
An isomorphism from
to is a bijection such that if , then . - We say that if an isomorphism between
and exists, then the two graphs are isomorphic, which we denote as . - Isomorphism is an equivalence class
- Adjacency is preserved under isomorphism.
- We say that if an isomorphism between
-
Given a graph
, the set of graphs isomorphic to forms an isomorphism class which partition the set of graphs with vertex set (where ) Isomorphism classes are orbits of
with the action defined on the subsets of . - (Godsil 2.3.1) The size of the isomorphism class containing
is - Proof: From the Orbit-Stabilizer Theorem. There are
permutations and by the definition of an automorphism.
- Proof: From the Orbit-Stabilizer Theorem. There are
- (Godsil 2.3.2) The number of isomorphism classes of graphs on
vertices is at most. -
Idea: Show that among the permutations of
with size , the maximum value of is realized by the permutation with exactly cycles of length . Let
. An orbit of corresponds to a clique of the vertices within the orbit. Hence, if has orbits on , then fixes graphs (every possible choice of clique subgraphs to include). Fix an even integer
and divide into three classes — the identity, the permutations containing support of size at most and the rest. The size of each class is given as Elements
and have orbit counts bounded as follows The result follows using Burnside’s lemma.
-
- (Godsil 2.3.1) The size of the isomorphism class containing