Cayley Graphs of Cyclic and Dihedral Groups

From Group Multiplication to Graph Edges

A Cayley graph records a group’s multiplication using edges: from each group element, follow each chosen generator to a neighboring element. For cyclic groups, one step generator traces a cycle. For dihedral groups, the choice of generators can produce either a cycle or a graph with two polygonal rims and connecting edges. The group is fixed, but its Cayley graph depends on the generating set.

Throughout, graphs are finite, simple and undirected. We use the following convention for a group \(G\) and a generating set \(S\): vertices are group elements, and a vertex \(g\) is adjacent to \(gs\) for every \(s\in S\). To obtain an undirected graph, \(S\) must be inverse-closed: whenever \(s\in S\), \(s^{-1}\in S\). We also require that the identity is not in \(S\), so the construction has no loops. The edge set consists of unordered pairs, so writing the same edge from its two endpoints does not create a multiple edge.

Changing from right multiplication to left multiplication is another common convention, but it can change how a labelled example is described. Here every adjacency calculation uses \(g\mapsto gs\). In particular, the order of factors matters when the group is not commutative.

Cyclic Groups and Their Step Sizes

Write the cyclic group of order \(n\) additively as \(\mathbb Z_n=\{0,1,\ldots,n-1\}\), with addition modulo \(n\). A step \(k\) and its inverse \(-k\) give the inverse-closed generating set \(S=\{k,-k\}\), provided these are distinct and nonzero. Then \(x\) is adjacent to \(x+k\) and \(x-k\), with all arithmetic taken modulo \(n\).

Proof. Put \(d=\gcd(n,k)\) and \(q=n/d\). Starting at \(x\), repeated steps of \(+k\) give the sequence \(x,x+k,x+2k,\ldots\), where the entries are reduced modulo \(n\). The first return to \(x\) occurs at the least positive integer \(j\) for which \(jk\) is divisible by \(n\). Dividing \(n\) and \(k\) by \(d\) shows that this least integer is \(q\). Thus the \(q\) vertices \(x,x+k,\ldots,x+(q-1)k\) are distinct, and the next step returns to \(x\). Because \(2k\not\equiv0\pmod n\), we have \(q\ge3\), so these steps form a cycle. Every edge changes a vertex by \(+k\) or \(-k\); therefore no edge leaves the set reached from \(x\), and that set is exactly its connected component. Finally, \(q=n\) exactly when \(d=1\). \(\square\)

Dihedral Groups: Rotations and Reflections

The dihedral group \(D_n\) is the symmetry group of a regular \(n\)-gon, with \(2n\) elements. Let \(r\) denote rotation by one position and \(s\) a reflection. Its presentation is \(r^n=e\), \(s^2=e\), and \(srs=r^{-1}\). Every element is uniquely of the form \(r^i\) or \(r^i s\), with \(i\) taken modulo \(n\). The relation implies \(sr=r^{-1}s\), which determines how right multiplication changes the labels.

Choose \(S=\{r,r^{-1},s\}\), for \(n\ge3\). The rotations \(r,r^{-1}\) are distinct, and each is its own partner under inversion; \(s=s^{-1}\). The adjacency rules are

For the second rule, for instance, \((r^i s)r=r^i(sr)=r^i r^{-1}s=r^{i-1}s\), while \((r^i s)s=r^i\). The graph has two cycles, one on the rotations and one on the reflections, with corresponding vertices joined by edges. This is the prism graph over \(C_n\).

Proof. The \(n\) elements \(e,r,\ldots,r^{n-1}\) are distinct and form a cycle under right multiplication by \(r\) and \(r^{-1}\). The \(n\) elements \(s,rs,\ldots,r^{n-1}s\) are distinct and form a second cycle: the displayed adjacency rule connects \(r^i s\) to \(r^{i-1}s\) and \(r^{i+1}s\). Right multiplication by \(s\) joins \(r^i\) to \(r^i s\) for every \(i\). These two sets are disjoint and contain all \(2n\) group elements, so this accounts for all vertices. Each vertex has exactly two neighbors along its own cycle and one across the joining edge, giving degree \(3\). Summing degrees gives \(2n\cdot3=6n\); every edge is counted at both endpoints, so the number of edges is \(6n/2=3n\). \(\square\)

Two Reflections Can Give a Different Graph

A different generating set for the same dihedral group can produce a different graph. Take \(S=\{s,sr\}\). Both elements are reflections and are involutions: \((sr)^2=srsr=r^{-1}r=e\). Their product \(s(sr)=r\), so the two reflections generate \(r\) as well as \(s\), and hence generate \(D_n\). The Cayley graph is now 2-regular, rather than 3-regular.

Proof. Starting from \(e\), alternate right multiplication by \(s\) and \(sr\). The resulting sequence is \(r^i,r^i s,r^{i+1}\) for each \(i\) modulo \(n\), because \(r^i\cdot s=r^i s\) and \((r^i s)(sr)=r^{i+1}\). Thus the cyclic sequence is \(e,s,r,rs,r^2,r^2s,\ldots,r^{n-1},r^{n-1}s,e\). Its \(2n\) entries before the return are distinct, since the rotation elements \(r^i\) are distinct, the reflection elements \(r^i s\) are distinct, and rotations are not reflections. Each consecutive pair is an edge from one of the two generators. Every vertex has degree \(2\), and these consecutive edges already form a cycle through all vertices; therefore there are no additional edges. \(\square\)

Common Pitfall: The Group Does Not Determine One Cayley Graph

A common error is to identify a Cayley graph from the group alone and overlook the generating set. For \(D_3\), the set \(\{r,r^{-1},s\}\) gives degree \(3\) at every vertex, whereas \(\{s,sr\}\) gives degree \(2\). These graphs cannot be the same: their degrees differ, and the first has two triangular cycles joined by three edges while the second is a 6-cycle.

For instance, a wrong calculation might claim that the graph from \(\{r,r^{-1},s\}\) is a 6-cycle because \(D_3\) has six elements. But the identity has three distinct neighbors, \(r\), \(r^{-1}=r^2\), and \(s\), so its degree is \(3\), not \(2\). A vertex on a cycle has degree \(2\). The correction is to calculate \(gS\) for a vertex before guessing the shape, and then check the labels around each proposed cycle.

These constructions show how group structure translates into graph structure. A cyclic generator gives a cycle when it reaches every group element; a non-generating step splits the graph into smaller cycles. In a dihedral group, adding a reflection to the rotation generators creates a pair of polygonal rims with joining edges, while two suitable reflections give one larger cycle. In every case, adjacency follows from the specified multiplication convention, not just from the geometric picture suggested by the group.