# Symmetry Group of a Complete Graph

The complete graph on $$n$$ vertices has exactly one edge joining each pair of distinct vertices, and is denoted by $$K_n$$

A symmetry of a graph $$\Gamma$$ is a bijection $$\alpha$$ taking vertices to vertices and edges to edges such that if $$Ends(e) = \{v,w\}$$, then $$Ends(\alpha(e)) = \{\alpha (v),\alpha(v)\}$$. The symmetry group of $$\Gamma$$ is the collection of all its symmetries. We note this group by $$Sym(\Gamma)$$

I am trying to show that $$Sym(K_n) \cong S_n$$. Here's what I have.

I think it is clear that $$|Sym (K_n)| \le n!$$, because there are $$n$$ ways to move the first vertex, $$n-1$$ ways to move the second, etc. (a priori this is an upper bound because I am only looking at the ways of moving the vertices). Thus, I just need to show that there is an injective homomorphism from $$S_n$$ to $$Sym(K_n)$$. Let $$\sigma \in S_n$$. Define $$\tilde{\sigma} : K_n \to K_n$$ to be $$\tilde{\sigma}(v_i) = v_{\sigma (i)}$$ and $$\tilde{\sigma}(e_i) = e_{\sigma (i)}$$, where $$v_i$$ is a vertex, $$e_i$$ an edge. it is easy to show that $$\tilde{\sigma}$$ is a bijection, but showing that it preserves adjacency is a little tougher. I need to show that $$Ends(e) = \{v_i,v_j\}$$ implies $$Ends(\tilde{\sigma}(e)) = \{\tilde{\sigma}(v_i),\tilde{\sigma}(v_j)\}$$.

I think uniqueness of edge might help, but I can't figure it out at the moment.

• What is $e_i$? If it is edge number $i$, then you can't write $\sigma(i)$ - $\sigma$ is defined only on $\{1, \ldots, n\}$, and graph has more then $n$ edges. – mihaild Apr 24 at 20:20
• @mihaild Hmm...You're right. How do we get $\sigma$ to act on both vertices and edges? – user193319 Apr 24 at 20:22
• As edge is pair of vertices, we can define $\tilde\sigma(\langle v_i, v_j\rangle) = \langle v_{\sigma(i)}, v_{\sigma(j)}\rangle$. This clearly preserves incidence. – mihaild Apr 24 at 20:26
• Your definition of a graph symmetry seems odd. $\alpha$ is a bijection on what? You have $\alpha$ applicable to either an edge or a vertex, but usually a graph symmetry is defined as a bijection on the set of vertices that happens to preserve adjacency (the “if” condition in your definition). One doesn’t usually think of a graph symmetry $\alpha$ as a function on both edges and vertices; instead one thinks of $\alpha$ as a function on vertices that (if it preserves adjacency) induces a natural action on the graph edges. Key fact for you: Every pair of vertices of $K_n$ are adjacent. – Steve Kass Apr 24 at 20:42
• Ah. I found the definitions from Meier in math.osu.edu/sites/math.osu.edu/files/Cayley.pdf, where a graph is defined as a set of vertices and edges, where the $Ends$ function associates edges to pairs of vertices. So at least, you should probably start by noting that the $Sym(K_n)$ is a subgroup of the symmetry group on the $n+e$ elements (vertices and edges) of $K_n$. Perhaps one way to proceed is to try showing that for each permutation in $S_n$ of the vertices alone, there is exactly one element of $Sym(K_n)$ that permutes the vertices in the same way. – Steve Kass Apr 25 at 14:24