Left Multiplication as a Graph Symmetry
A Cayley graph records how multiplying group elements by selected generators moves from one vertex to another. The group itself supplies a natural family of permutations of its vertices: multiply every vertex on the left by the same group element. The key fact is that this operation respects edges defined by multiplication on the right. Moreover, choosing the left multiplier appropriately sends any specified vertex to any other. Together, these facts explain why Cayley graphs are vertex-transitive.
In this convention, an edge joins \(g\) to \(gs\): the generator is multiplied on the right. A graph automorphism is a bijection of the vertex set that preserves adjacency in both directions. A graph is vertex-transitive if, for every two vertices \(x,y\), some automorphism sends \(x\) to \(y\).
The generating assumption ensures that the graph is connected, but it is not needed for the symmetry result below. The same proof works if \(S\) is not a generating set; in that case the graph may be disconnected. If \(G\) is the trivial group, then \(S=\varnothing\), and the graph has one vertex and no edges. The result also applies to that case.
The Left-Multiplication Theorem
Proof. Fix \(a\in G\). The map \(L_a\) is a bijection: its inverse is \(L_{a^{-1}}\), since \(a^{-1}(ag)=g\) and \(a(a^{-1}g)=g\) for every \(g\in G\). Now let \(\{g,gs\}\) be any edge, where \(s\in S\). Its image under \(L_a\) is \(\{ag,ags\}=\{ag,(ag)s\}\), which is again an edge by the definition of the Cayley graph. Thus \(L_a\) sends edges to edges. Applying the same edge-preservation argument to its inverse \(L_{a^{-1}}\) shows that adjacency is preserved in both directions; hence \(L_a\) is an automorphism.
To prove transitivity, take any \(x,y\in G\) and set \(a=yx^{-1}\). Then \(L_a(x)=(yx^{-1})x=y\). Thus a left multiplication sends \(x\) to \(y\), as required. This includes the one-vertex case, where \(x=y=1\) and \(a=1\). Finally, the maps compose according to \(L_a\circ L_b=L_{ab}\), and \(L_a^{-1}=L_{a^{-1}}\), so they form a group of automorphisms. \(\square\)
The adjacency calculation works because left multiplication leaves the right-hand generator unchanged: the step from \(g\) to \(gs\) becomes the step from \(ag\) to \((ag)s\). This is the specific feature of the convention used here. It does not say that every permutation arising from group multiplication preserves the graph.
Worked Example: A Cayley Graph of the Cyclic Group of Order Four
Use additive notation for \(G=\mathbb{Z}_4=\{0,1,2,3\}\), with addition modulo \(4\), and take \(S=\{1,3\}\). The set \(S\) excludes \(0\), is closed under additive inverses because \(-1=3\) and \(-3=1\) modulo \(4\), and generates \(\mathbb{Z}_4\). The graph has vertex set \(\{0,1,2,3\}\). Adding each generator gives the neighbors:
- From \(0\): \(0+1=1\) and \(0+3=3\).
- From \(1\): \(1+1=2\) and \(1+3=0\).
- From \(2\): \(2+1=3\) and \(2+3=1\).
- From \(3\): \(3+1=0\) and \(3+3=2\), with all sums taken modulo \(4\).
After duplicate unordered pairs are counted only once, the edge set is \(\{01,12,23,03\}\). Consider the left translation \(L_2(x)=2+x\pmod 4\). It sends \(0\mapsto2\), \(1\mapsto3\), \(2\mapsto0\), and \(3\mapsto1\). Its images of the four edges are \(01\mapsto23\), \(12\mapsto30\), \(23\mapsto01\), and \(03\mapsto12\), all of which are edges in the list.
Check: The translation is its own inverse, since \(2+2=0\pmod 4\), so it indeed permutes the edge set in both directions. It sends vertex \(1\) to vertex \(3\), illustrating the transitivity construction: the required shift is \(3-1=2\pmod 4\).
A Nonabelian Example
In a nonabelian group, the order of multiplication matters, so it is useful to compute the edges explicitly. Let \(G=S_3\), the group of permutations of \(\{1,2,3\}\), with products composed right to left. Put \(a=(12)\), \(b=(23)\), and \(S=\{a,b\}\). Both generators are their own inverses. The six group elements are \(e,a,b,c,d,z\), where \(e\) is the identity, \(c=ab=(123)\), \(d=ba=(132)\), and \(z=aba=(13)\).
Worked Example: Left Multiplication in the Cayley Graph of \(S_3\)
Compute the two right-generator neighbors \(ga\) and \(gb\) for each vertex \(g\). The products are:
| \(g\) | \(ga\) | \(gb\) |
|---|---|---|
| \(e\) | \(a\) | \(b\) |
| \(a\) | \(e\) | \(c\) |
| \(b\) | \(d\) | \(e\) |
| \(c=ab\) | \(z\) | \(a\) |
| \(d=ba\) | \(b\) | \(z\) |
| \(z=aba\) | \(c\) | \(d\) |
For instance, \(ca=aba=z\), \(cb=abb=a\), \(da=baa=b\), and \(db=bab=z\). Thus, after duplicate unordered pairs are removed, the edge set is \(\{ea,eb,ac,bd,cz,dz\}\). These are the six consecutive edges in the cycle \(e,a,c,z,d,b,e\).
Now apply \(L_a(g)=ag\). Its values are \(L_a(e)=a\), \(L_a(a)=e\), \(L_a(b)=c\), \(L_a(c)=b\), \(L_a(d)=z\), and \(L_a(z)=d\). The six edges map as follows: \(ea\mapsto ea\), \(eb\mapsto ac\), \(ac\mapsto eb\), \(bd\mapsto cz\), \(cz\mapsto bd\), and \(dz\mapsto dz\). Every image is an edge, and \(L_a\) is its own inverse, so this verifies directly that it is an automorphism. Also, \(L_b(a)=ba=d\), so a left multiplication sends \(a\) to \(d\).
Check: The edge list has six distinct edges, matching the six consecutive pairs around the displayed cycle. The theorem’s formula for sending \(x=a\) to \(y=d\) gives \(yx^{-1}=da\). Since \(d=ba\) and \(a^2=e\), \(da=baa=b\); indeed \(L_b(a)=ba=d\).
This calculation illustrates both parts of the theorem. The local rule “multiply on the right by \(a\) or \(b\)” is unchanged by left multiplication, even though the group is nonabelian. And the formula \(yx^{-1}\) gives a specific multiplier for any chosen ordered pair of vertices.
Why Right Multiplication Is Different
A tempting but generally incorrect claim is that right multiplication must also preserve the graph. If \(R_a(g)=ga\), then an edge \(\{g,gs\}\) maps to \(\{ga,gsa\}\). Relative to the first image vertex \(ga\), the second is reached by right multiplication by \(a^{-1}sa\), since \((ga)(a^{-1}sa)=gsa\). That conjugated generator need not belong to \(S\). Thus the left-multiplication proof cannot simply be repeated with the multiplication order reversed.
Worked Example: A Right Multiplication That Does Not Preserve Adjacency
Use the graph \(\operatorname{Cay}(S_3,\{a,b\})\) above, and consider \(R_a(g)=ga\). The edge \(eb\) is present because \(b\in S\). Under \(R_a\), its endpoints map to \(R_a(e)=a\) and \(R_a(b)=ba=d\), so the image pair is \(\{a,d\}\).
To test whether this is an edge, compare its endpoints using the right-generator rule. Starting at \(a\), the second endpoint would have to be \(as\) for \(s\in\{a,b\}\). The two possibilities are \(aa=e\) and \(ab=c\), neither of which is \(d\). Equivalently, \(a^{-1}d=aba=z\notin\{a,b\}\). Therefore \(\{a,d\}\) is not an edge, and \(R_a\) is not an automorphism.
Check: The explicit edge set is \(\{ea,eb,ac,bd,cz,dz\}\), which does not contain \(ad\). In the conjugation calculation, \(a^{-1}ba=aba=z\), and \(z\) is not one of the chosen generators. The failed adjacency test agrees with the edge list.
What the Symmetry Gives
Vertex-transitivity means that no vertex is distinguished by the graph’s automorphisms: any one can be moved to any other while preserving adjacency. In a Cayley graph, this conclusion does not require the graph to be complete, or even connected. The proof comes from the group operation and the right-generator definition of the edges.
It also explains why checks at one vertex can often be transported to another. For example, an automorphism taking \(x\) to \(y\) gives a bijection from the neighbors of \(x\) to the neighbors of \(y\): adjacency preservation sends each neighbor of \(x\) to a neighbor of \(y\), and the inverse automorphism gives the reverse correspondence. This is a consequence of the automorphism property, not an additional assumption about the generating set.
Common pitfall: Do not confuse “the group acts by left multiplication” with “the edges are defined by left multiplication.” Here edges are \(\{g,gs\}\), with the generator on the right; the symmetry is left multiplication \(g\mapsto ag\). In a nonabelian group, changing the order changes the calculation, as the \(S_3\) example shows.
Check Your Understanding
For each question, use the convention that an edge joins \(g\) to \(gs\).
- Which conditions on \(S\) make \(\operatorname{Cay}(G,S)\) a simple undirected graph under this definition?
- For \(x,y\in G\), verify directly that \(L_{yx^{-1}}(x)=y\).
- In \(\operatorname{Cay}(\mathbb{Z}_4,\{1,3\})\), compute the images of edges \(12\) and \(03\) under translation by \(1\).
- In the \(S_3\) example, why does left multiplication preserve an edge \(\{g,gs\}\) without changing the generator \(s\)?
- For a right multiplication \(R_a\), what condition on \(a^{-1}sa\) would ensure that the image of an edge using generator \(s\) is again an edge?