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.

  • $\begingroup$ 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. $\endgroup$ – mihaild Apr 24 at 20:20
  • $\begingroup$ @mihaild Hmm...You're right. How do we get $\sigma$ to act on both vertices and edges? $\endgroup$ – user193319 Apr 24 at 20:22
  • 2
    $\begingroup$ 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. $\endgroup$ – mihaild Apr 24 at 20:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Steve Kass Apr 24 at 20:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Steve Kass Apr 25 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.