Each group element becomes a vertex. Each generator becomes an edge color. The algebra turns into a graph you can walk.
A Cayley graph turns a finite group into geometry. Pick a generating set S, vertices are group elements, edges go from g to gs whenever s ∈ S.
The graph encodes the group. Distance is the word metric — the minimum number of generators in a word equal to g. Conjugacy classes cluster; cycles are relations among generators; normal subgroups produce quotient maps. For classical families (symmetric, dihedral, quaternion, alternating), the Cayley graph is often a known polytope.
This article walks through six Cayley graphs, from S3's hexagon up to S5's 120-vertex graph. The permutohedron reappears as S4's Cayley graph; regular polytopes reappear as Cayley graphs of their symmetry groups.
| Group | Order | Generators used | Cayley graph shape |
|---|---|---|---|
| 6 | (1 2), (2 3) | hexagon | |
| 24 | (1 2), (2 3), (3 4) | truncated octahedron | |
| 120 | (1 2), (2 3), (3 4), (4 5) | 4D permutohedron | |
| 8 | i, j | cube-like (4-regular) | |
| 12 | r, s (rotation, reflection) | hexagonal prism | |
| 60 | (1 2 3 4 5), (1 2)(3 4) | truncated icosahedron |
Table 1. Six finite groups, the generating sets chosen below, and the resulting Cayley graph shapes. Different generating sets give different graphs for the same group. All of these are Cayley graphs in the classical sense: vertices labelled by group elements, edges colored by generators.
The symmetric group has six elements: the six permutations of . Take generators and . The Cayley graph has six vertices, and from each vertex there is one red edge (multiply by ) and one blue edge (multiply by ). Because both generators are involutions, the edges are undirected: the same edge goes both ways. The resulting graph is a hexagon.
Figure 1. The Cayley graph of with generators (red) and (blue). The six vertices are the permutations written in one-line notation. The graph is a hexagon whose edges alternate red and blue as you walk around it. Alternating the two generators traces a Hamiltonian cycle: . The number of red–blue alternations needed to reach a vertex from the identity is its word length.
The walk eventually returns to the identity because in S3. Every Cayley graph is generators-and-relations; the relations are exactly the closed walks.
Four objects have 24 permutations. With the three adjacent transpositions , the Cayley graph has 24 vertices and 36 edges. Each vertex has three neighbors, one for each generator. The graph is the edge skeleton of the truncated octahedron, the permutohedron from article 17.
In parallel coordinates, each of the 24 permutations becomes a polyline over four axes (the four positions). Two polylines represent adjacent vertices in the Cayley graph when they differ by a single adjacent transposition, meaning they agree on all but two consecutive positions, and the two disagreeing positions are a swap of a pair whose values differ by one from each other's positions. Because each transposition is an odd permutation, a single edge flips the sign of the permutation. Color the polylines by sign and the graph becomes a bipartite structure: every edge connects an even (blue) vertex to an odd (red) vertex. This is the algebraic statement that is a subgroup of index 2.
Figure 2. The Cayley graph of under adjacent transpositions. Left: 2D projection of the truncated octahedron, with edges colored by generator (red , blue , green ). Right: 24 polylines, one per permutation. Color switches between sign (bipartite) and inversion count (word distance from identity). The structure matches the permutohedron from article 17 exactly: the Cayley graph of a Coxeter group under its standard generators is the 1-skeleton of its W-permutohedron.
The quaternion group has eight elements: . The multiplication satisfies , together with the rule that commutes with everything. With generators , every element is reachable by a word of length at most three. The Cayley graph is 4-regular (two generators, but each has an inverse distinct from itself: and , both of order 4), and has 8 vertices and 16 edges.
Unlike D4 of the same order, Q8 has every subgroup normal yet remains non-commutative. Walking ij vs. ji from the identity ends at different vertices.
Figure 3. The quaternion group . Left: Cayley graph with blue edges for right-multiplication by and red edges for right-multiplication by ; arrows indicate direction because and are not their own inverses. Right: the 8×8 multiplication table as a heatmap; each cell is colored by its product. The non-abelian structure shows up as the table's lack of symmetry across the diagonal, and in the Cayley graph as distinct endpoints for walks and .
In Q8, ij = k and ji = −k. The blue-red square doesn't close: blue-then-red and red-then-blue land at antipodal vertices k and −k.
The dihedral group is the group of symmetries of a regular hexagon: six rotations and six reflections, 12 elements total. Generators: a rotation by 60 degrees and a reflection . Then every element is either (a rotation by steps) or (a rotation followed by a reflection). The presentation is .
The Cayley graph of is a hexagonal prism: two hexagons (one of rotations, one of reflections) joined by six reflection-edges. Walking around the outer hexagon is the subgroup of rotations; stepping across any rung applies a reflection. The alternating product produces walks that spiral between the two hexagons. Because every reflection-edge is undirected.
Figure 4. The dihedral group . Left: the regular hexagon acted on by the selected element: rotations cycle the vertices, reflections fix an axis. Right: the Cayley graph with generators (blue rotation edges forming two concentric hexagons, traversed with arrows because ) and (red reflection rungs between them). Top hexagon: rotations . Bottom hexagon: reflections .
The alternating group has 60 elements: the even permutations of . It is the smallest non-abelian simple group and is isomorphic to the group of rotations of a regular icosahedron. In parallel coordinates with 5 axes, all 60 permutations become polylines on integer values .
has exactly five conjugacy classes. Their sizes are 1, 12, 12, 15, 20: one identity, two distinct classes of 5-cycles (which are conjugate in but split in ), one class of 15 double-transpositions, and one class of 20 three-cycles. Color the polylines by conjugacy class and the geometry of emerges: the 20 three-cycles all fix two positions, so they form a tight bundle; the 15 double-transpositions disturb four coordinates and look like disjoint pair-swaps; the 5-cycles fill out the wilderness.
Figure 5. as parallel coordinates. Left: 60 polylines across 5 axes, one per even permutation, colored by conjugacy class. Right: the class-size breakdown as a stacked-bar partition of 60. is the smallest non-abelian simple group and is a rotation group of the icosahedron. In the full Cayley graph under a generating set like , looks like a truncated icosahedron, too dense to draw every edge here, but the conjugacy bundle structure in the PC panel is the shadow of that polytope.
Conjugacy in a group is the equivalence relation . Conjugacy classes partition the group. In the Cayley graph they do not form subgraphs (a class is rarely closed under multiplication) but they form visible clusters when the graph is embedded sensibly.
has exactly five conjugacy classes, one for each partition of 4:
In parallel coordinates, each class has a distinct signature. The identity is a single monotone polyline . The six transpositions are polylines that cross exactly twice. The three double-transpositions cross four times but in two independent pairs. The eight 3-cycles shift three positions in a cyclic way. The six 4-cycles shift all four positions.
Figure 6. The five conjugacy classes of , corresponding to the five partitions of 4. Each class has a geometric signature in parallel coordinates. The class sizes 1, 6, 3, 8, 6 sum to and satisfy where is the cycle type. Conjugacy classes govern character theory: has exactly 5 irreducible representations, one per conjugacy class.
The word metric on a Cayley graph counts the minimum number of edges needed to get from one vertex to another, equivalently the minimum length of a word in the generators that equals . For the symmetric group under adjacent transpositions, the word metric from the identity has a name from statistics: the Kendall tau distance, also known as the inversion count. A permutation's distance from the identity is the number of pairs of positions that are out of sorted order.
The distance distribution, the number of group elements at each distance from the identity, is called the growth function of the group. For under adjacent transpositions, these numbers are the Mahonian numbers: coefficients of the , the -factorial. They are symmetric, peaked in the middle, and sum to .
Figure 7. The word metric for under adjacent transpositions. Left: histogram of distances from the identity. These are the Mahonian numbers. For the sequence is 1, 3, 5, 6, 5, 3, 1 (sum 24, diameter ). For the sequence is 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1 (sum 120, diameter ). Right: all permutations as polylines, with opacity scaled by distance from the identity. The reverse permutation is the farthest point, the antipode, at distance .
Finite Cayley graphs are rigid metric spaces. Diameter, girth, and expansion connect to representation theory. For Sn under adjacent transpositions, the diameter is exactly n(n−1)/2, achieved by the reverse permutation. The Weyl group of E₈ has order 696,729,600 and Cayley diameter 120.
Subgroups are subgraphs, cosets are sheets, normal subgroups are fiber bundles over the quotient graph. The number of conjugacy classes equals the number of irreducible representations.
When a Cayley graph is a polytope in 4D+, parallel coordinates draw the vertex polylines and conjugacy classes stay readable. For Weyl groups of E₈, exceptional root systems, or sporadic simple groups, drawing every element is out of reach but the conjugacy partition remains legible.
The next article looks at knot invariants as high-dimensional signatures.