Cayley Graphs

Every abstract group has a shape. Cayley graphs make that shape visible.

Why this matters

Cayley graphs connect algebra to combinatorics and geometry. They appear in the study of word problems in group theory, in the design of efficient communication networks, in the analysis of Rubik’s cube state spaces, and as fundamental objects in geometric group theory — a field that treats groups themselves as geometric spaces.

The construction

Let $G$ be a group and $S \subseteq G$ a set of generators (a set whose elements, combined in various ways, can produce every element of $G$ ). The Cayley graph $\text{Cay}(G, S)$ is a directed graph where:

Each node represents one element of $G$ .
For each element $g \in G$ and each generator $s \in S$ , there is a directed edge from $g$ to $g \cdot s$ (right-multiplication by $s$ ).

The edges are colored or labeled by generator — one color per generator. The resulting picture is a graph where you can “read off” the group’s multiplication structure visually.

Explore: the dihedral group D₄

The dihedral group $D_4$ is the group of symmetries of a square. It has 8 elements:

Element	Meaning
$e$	identity (no change)
$r$	rotation 90° clockwise
$r^2$	rotation 180°
$r^3$	rotation 270° clockwise
$s$	reflection (horizontal axis)
$sr$	reflection, then rotate 90°
$sr^2$	reflection, then rotate 180°
$sr^3$	reflection, then rotate 270°

The group has the presentation $\langle r, s \mid r^4 = s^2 = e, \; rs = sr^{-1} \rangle$ .

The Cayley graph below uses generators $\{r, s\}$ . Click “Apply r” or “Apply s” to move through the graph from the identity. Watch how the path you trace records the word you have written in the generators.

Current: e (identity)

rotation r

reflection s

your path

current position

Things to try:

Apply $r$ four times. You return to $e$ — because $r^4 = e$ .
Apply $s$ twice. You return to $e$ — because $s^2 = e$ .
Apply $r$ then $s$ then $r^{-1}$ (= $r^3$ ) then $s$ . Where do you end up? This traces the relation $rs = sr^{-1}$ in the graph.

What the structure tells you

Several features of $D_4$ are immediately visible in the Cayley graph:

The blue $r$ -edges form two directed 4-cycles — one through the rotations $\{e, r, r^2, r^3\}$ and one through the reflections $\{s, sr, sr^2, sr^3\}$ . This tells you that the subgroup generated by $r$ alone has order 4.
The red $s$ -edges are bidirectional (since $s^2 = e$ ) and connect each rotation to a distinct reflection. Applying $s$ twice always returns to the start.
Every node has the same in-degree and out-degree — this is always true for Cayley graphs, because the group acts regularly on itself.

Worked example — ℤ/4ℤ Cayley graph

The simplest non-trivial Cayley graph: $\mathbb{Z}/4\mathbb{Z}$ with generator $S = \{1\}$ .

Nodes: $0, 1, 2, 3$ .
Edges: $0 \to 1 \to 2 \to 3 \to 0$ (each node maps to the next via $+1 \pmod{4}$ ).

The result is a directed 4-cycle. Every element of $\mathbb{Z}/4\mathbb{Z}$ is reached by applying the generator $1$ repeatedly, which confirms that $1$ generates the whole group.

A key theorem

Cayley’s theorem (1854): Every group $G$ is isomorphic to a subgroup of the symmetric group $\text{Sym}(G)$ . In other words, every abstract group can be represented as a group of permutations.

The Cayley graph makes this concrete: the group acts on itself by right-multiplication, and each generator induces a permutation of the nodes.

Common misconception

The Cayley graph of a group depends on the choice of generators. The same group $\mathbb{Z}/6\mathbb{Z}$ with generator $\{1\}$ produces a directed 6-cycle; with generators $\{2, 3\}$ it produces a denser graph. The generators are not a property of the group — they are a choice. Different choices reveal different aspects of the same structure.

Self-check

In a Cayley graph Cay(G, S), what do the nodes represent?

The generators in SThe elements of the group GThe subgroups of GThe relations in the group presentation

In the D4 Cayley graph with generators {r, s}, applying r four times from any node returns you to the starting node. Why?

Because D4 has 4 generatorsBecause r has order 4 in D4, meaning r⁴ = eBecause the graph has 4-fold symmetryBecause s cancels r in 4 steps

If you change the generating set S for the same group G, what changes?

The group G itself changesThe number of nodes in the Cayley graphThe structure of the Cayley graph (edges, shape, density)Nothing — all Cayley graphs of a group are identical