1
$\begingroup$

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?

2 Answers 2

2

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?

1

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)!$.