# Prove that the group of automorphisms of a labelled Cayley graph of a group G is the group G itself (Just stumped on one direction)

I feel like for this question it is just a matter of showing the mapping in both directions, from the group to the graph and the graph to the group.

So for the mapping from the group to the graph, I mapped the each group action in G to some path that a vertex will travel. The path will be composed of the edges corresponding to the generators of the group action. I then chose some arbitrary vertex and showed that mapping it in such a way is an automorphism as the ends would be the same. In these automorphisms, every vertex follows the same type of path (generator/edge sequence) to reach it's mapped vertex.

Now, for the other direction I am a little stuck. I initially tried to prove by contradiction: Suppose there exists an automorphism that does not map according to a group action. This would mean the generator/edge sequence would be different for each vertex. I then noted that there must exist one edge e such that it's end vertices will follow different generator/edge sequences to reach it's mapped destination. However, I realized that it's possible for them to still be neighbors after the mapping. I hope I haven't overlooked anything or interpreted graph automorphisms wrong!

• What do you mean by "labelled Cayley graph". – Chris Godsil Feb 10 '13 at 0:07
• I think just the associated cayley graph that has the group elements labelled on the vertices. I'm not too sure though, I was just dealing with it that way – Azhuang Feb 10 '13 at 0:40
• Well, the complete graph $K_n$ is a Cayley graph for any group of order $n$, and its automorphism group is the symmetric group $\mathrm{Sym}(n)$. – Chris Godsil Feb 10 '13 at 0:43
• Ahh yeah, maybe it has something to do with the generators chosen - I'll have to get more details. Thanks! – Azhuang Feb 10 '13 at 2:15
• Is there any restriction on Cayley graphs that would make the question claim true? – Azhuang Feb 10 '13 at 4:20

The Cayley graph $\Gamma = \Gamma(G,X)$ of a group $G$ is defined with respect to a generating set $X$ of $G$. It has the elements of $G$ as vertices and, for each $g \in G$ and $x \in X \cup X^{-1}$, a directed edge labelled $x$ from $g$ to $gx$. An edge labelled $x$ is often identified with the edge labelled $x^{-1}$ in the other direction. Since $X$ generates $G$, $\Gamma$ is connected.
For each $h \in G$, we can define a map $T_h$ (translation by $h$) $\Gamma \to \Gamma$ by $T_h:g \mapsto hg$ for $g \in G$. Then it is easy to see that $T_h \in {\rm Aut}(\Gamma)$ and $h \mapsto T_h$ is an injective homomorphism $G \to {\rm Aut}(\Gamma)$, so we can identify $G$ with a subgroup of ${\rm Aut}(\Gamma)$. This subgroup acts regularly (i.e. transitively and with trivial stabilizers) on $\Gamma$, so to prove that it is equal to ${\rm Aut}(\Gamma)$, it is sufficient to prove that the stabilizer in ${\rm Aut}(\Gamma)$ of a vertex in $\Gamma$ is trivial.
The directed edges from a vertex $g$ in $\Gamma$ all have different labels (they do not necessarily have distinct targets, but that doesn't matter), and so an automorphism of the labelled graph that fixes $g$ must fix all vertices with source $g$ and hence, since $\Gamma$ is connected, it must fix all vertices and hence is trivial.