# Proof: the symmetry group of a complete graph is vertex transitive

The following self-contained post relates to definition 1.17, p. 11, of the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier.

Let $K_n$ be a complete graph and $\mbox{Sym}(K_n)$ its symmetry group. It will be shown that $K_n$ is vertex transitive, i.e. that for any two vertices $v_i\in K_n$ and $v_j\in K_n$ there exists a symmetry $a\in\mbox{Sym}(K_n)$ such that $a(v_i)=v_j$.

The proof is constructive. Given any two vertices $v_i\in K_n$ and $v_j\in K_n$, it suffices to provide a symmetry $a_{ij}:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)\in\mbox{Sym}(K_n)$ such that $a_{ij}(v_i)=v_j$. Although the suggested symmetry is different for every $v_i$ and $v_j$, the simpler notation $a$ is preferred in place of $a_{ij}$.

Given $v_i\in K_n$ and $v_j\in K_n$, a suitable symmetry can be constructed by swapping $v_i$ with $v_j$, by redirecting all edges with one end in $v_i$ to edges with one end in $v_j$ and vice versa, and by leaving all other vertices and edges intact.

To formalize the construction, given $v_i\in K_n$ and $v_j\in K_n$, the symmetry $a$ is set to satisfy the following seven properties:

• $a(v_i)=v_j$,
• $a(v_j)=v_i$,
• $a(v_k)=v_k$ for all vertices $v_k$ other than $v_i,~v_j$,
• $a(e_{ij})=e_{ij}$, where $e_{ij}$ denotes the edge connecting $v_i$ with $v_j$,
• $a(e_{ik})=e_{jk}$ for all $k$ other than $i,~j$, where $e_{ik}$ denotes the edge connecting $v_i$ with $v_k$ and $e_{jk}$ the edge connecting $v_j$ with $v_k$,
• $a(e_{jk})=e_{ik}$ for all $k$ other than $i,~j$, and
• $a(e_{kl})=e_{kl}$ for all $k,~l$ other than $i,~j$, where $e_{kl}$ denotes the edge connecting $v_k$ with $v_l$.

Note that all edges exist in the above construction since $K_n$ is complete, so the symmetry is well-defined.

It is easy to check that the proposed symmetry maps vertices to vertices, edges to edges, and preserves the connectivity of $\Gamma$ according to the definition of symmetry provided in this blog post. For instance, $\mbox{ends}(e_{ik})=\{v_i,v_k\}$, $a(e_{ik})=e_{jk}$, $a(v_i)=v_j$ and $a(v_k)=v_k$ yield $\mbox{ends}(a(e_{ik}))=\mbox{ends}(e_{jk})=\{v_j,v_k\}=\{a(v_i),a(v_k)\}$, which is an edge in $K_n$.