Editing Cayley graph (section)

== Characterization ==
The group <math>G</math> [[Group action (mathematics)|acts]] on itself by left multiplication (see [[Cayley's theorem]]). This may be viewed as the action of <math>G</math> on its Cayley graph. Explicitly, an element <math>h\in G</math> maps a vertex <math>g\in V(\Gamma)</math> to the vertex <math>hg\in V(\Gamma).</math> The set of edges of the Cayley graph and their color is preserved by this action: the edge <math>(g,gs)</math> is mapped to the edge <math>(hg,hgs)</math>, both having color <math>c_s</math>. In fact, all [[Graph automorphism|automorphisms]] of the colored directed graph <math>\Gamma</math> are of this form, so that <math>G</math> is isomorphic to the [[symmetry group]] of <math>\Gamma</math>.{{NoteTag|Proof: Let <math>\sigma : V(\Gamma) \to V(\Gamma)</math> be an arbitrary automorphism of the colored directed graph <math>\Gamma</math>, and let <math>h = \sigma(e)</math> be the image of the identity. We show that <math>\sigma(g) = hg</math> for all <math>g\in V(\Gamma)</math>, by induction on the edge-distance of <math>g</math> from <math>e</math>. Assume <math>\sigma(g) = hg</math>. The automorphism <math>\sigma</math> takes any <math>c_s</math>-colored edge <math>g\to gs</math> to another  <math>c_s</math>-colored edge <math>\sigma(g)\to\sigma(gs)</math>. Hence <math>\sigma(gs) = \sigma(g)s = hgs</math>, and the induction proceeds. Since <math>\Gamma</math> is connected, this shows <math>\sigma(g) = hg</math> for all <math>g\in V(\Gamma)</math>.}}{{NoteTag|It is easy to modify <math>\Gamma</math> into a simple graph (uncolored, undirected) whose symmetry group is isomorphic to <math>G</math>: replace colored directed edges of <math>\Gamma</math> with appropriate trees corresponding to the colors.|name=note 2}} 

The left multiplication action of a group on itself is [[simply transitive]], in particular, Cayley graphs are [[vertex-transitive graph|vertex-transitive]]. The following is a kind of converse to this:

{{math theorem | name = Sabidussi's Theorem | math_statement = An (unlabeled and uncolored) directed graph <math>\Gamma</math> is a Cayley graph of a group <math>G</math> if and only if it admits a simply transitive action of <math>G</math> by [[graph automorphism]]s (i.e., preserving the set of directed edges).<ref>{{cite journal|first= Gert |last=Sabidussi|author-link=Gert Sabidussi | journal=[[Proceedings of the American Mathematical Society]] |date=October 1958 |volume=9 |number=5 | pages=800–4 | title=On a class of fixed-point-free graphs |jstor=2033090 |doi=10.1090/s0002-9939-1958-0097068-7|doi-access=free }}</ref>}}

To recover the group <math>G</math> and the generating set <math>S</math> from the unlabeled directed graph <math>\Gamma</math>, select a vertex <math>v_1\in V(\Gamma)</math> and label it by the identity element of the group. Then label each vertex <math>v</math> of <math>\Gamma</math> by the unique element of <math>G</math> that maps <math>v_1</math> to <math>v.</math> The set <math>S</math> of generators of <math>G</math> that yields <math>\Gamma</math> as the Cayley graph <math>\Gamma(G,S)</math> is the set of labels of out-neighbors of <math>v_1</math>. Since <math>\Gamma</math> is uncolored, it might have more directed graph automorphisms than the left multiplication maps, for example group automorphisms of <math>G</math> which permute <math>S</math>.