I am reading Sanjeev Arora and Barak Boaz. I am stuck at proving the following which the book assumes to be trivial result. Following are the point I am stuck at
If we are given a graph $G$ ( with $n$ vertices ) then the size of the set $S=\{(H,\pi)\mid H\text{ is isomorphic to G and }\pi \text{ is one of the automorphisms of } H\}$ is $n!$.
I would really appreciate any hints.
Consider the symmetric group $S_n$ acting on the set of all graphs on $n$ fixed vertices, with action the obvious one: relabel the vertices via permutation.
Let $\mathcal{O}$ be the orbit of $G$ under this action. I claim that the result is just the orbit-stabilizer theorem applied to $\mathcal{O}$.
In fact, $(H,\pi) \in S$ if and only if $\pi(H) = H$, so we can identify $S$ with the disjoint union $\sqcup_{H\in\mathcal{O}} \rm{Stab}(H)$. Since all the stabilizers are the same size, we get $|S| = |\mathcal{O}|\cdot|\rm{Stab}(G)| = |S_n| = n!$.