Working out the number of automorphisms of a graph Take the complete graph with n vertices, where one edge has been removed. How can you work out the number of automorphisms that this graph has?
 A: HINT: Let $G$ be the graph remaining after you remove the edge between vertices $u$ and $v$ in $K_n$, and let $V'=V\setminus\{u,v\}$, where $V$ is the vertex set of $K_n$. In $G$ the vertices $u$ and $v$ ‘look alike’ in every respect, and all of the vertices in $V'$ also ‘look alike’ in every respect. Thus, if $h$ is an automorphism of $G$, then $h$ must permute the set $\{u,v\}$ and the set $V'$. Conversely, any bijection from $V$ to $V$ that permutes both $\{u,v\}$ and $V'$ is an automorphism of $G$.
Can you take it from there?
A: Let the graph be $G=(V,E)$ with vertex set $$V=\{v_1,v_2,\ldots,v_{n-2}\} \cup \{u_1,u_2\}$$ and edge set $$E=\{v_i v_j : i,j \in \{1,2,\ldots,n-2\} \text{ and } i \neq j\} \cup \{v_i u_j: i \in \{1,2,\ldots,n-2\} \text{ and } j \in \{1,2\}\}.$$
The vertices $u_1$ and $u_2$ have degree $n-2$ whereas the vertices $v_i$ have degree $n-1$.  The degree of a vertex is an example of a vertex invariant; vertex invariants are preserved under isomorphism.  In this case, any automorphism must map a vertex of degree $d$ to another vertex of degree $d$.
Hence $\{v_1,v_2,\ldots,v_{n-1}\}$ and $\{u_1,u_2\}$ are preserved setwise by any automorphism.

*

*Claim: Every $\alpha \in \mathrm{Sym}(\{v_1,v_2,\ldots,v_{n-1}\})$ is an automorphism.
Applying the isomorphism $\alpha$ gives a graph with edge set $$\{v_{\alpha(i)} v_{\alpha(j)} : i,j \in \{1,2,\ldots,n-2\} \text{ and } i \neq j\} \cup \{v_{\alpha(i)} u_{\alpha(j)}: i \in \{1,2,\ldots,n-2\} \text{ and } j \in \{1,2\}\}$$ which equals $E$ (since $\{1,2,\ldots,n-2\}$ is fixed setwise by $\alpha$).


*Claim: The transposition $\beta:=(u_1,u_2)$ is an automorphism.
Applying the isomorphism $\beta$ gives a graph with edge set $$\{v_i v_j : i,j \in \{1,2,\ldots,n-2\} \text{ and } i \neq j\} \cup \{v_i u_{\beta(j)}: i \in \{1,2,\ldots,n-2\} \text{ and } j \in \{1,2\}\}$$ which equals $E$ (since $\{1,2\}$ is fixed setwise by $\beta$).
We conclude that any isomorphism which preserves $\{v_1,v_2,\ldots,v_{n-1}\}$ and $\{u_1,u_2\}$ setwise is an automorphism.
So the automorphism group of $G$ is isomorphic to $$\mathrm{Sym}(\{v_1,v_2,\ldots,v_{n-1}\}) \times \mathrm{Sym}(\{u_1,u_2\})$$ which has size $2\, (n-2)!$.
