Cayley Graph — Definition, Formula & Examples

A Cayley graph is a graph that represents the structure of a group by connecting group elements according to a chosen set of generators. Each vertex is a group element, and a directed edge links element

g

to element

gs

for every generator

s

Given a group $G$ and a generating set $S \subseteq G$ with $e \notin S$ , the Cayley graph $\text{Cay}(G, S)$ is a directed graph whose vertex set is $G$ and whose edge set is $\{(g,\, gs) \mid g \in G,\, s \in S\}$ . If $S$ is closed under inverses ( $S = S^{-1}$ ), the graph is typically treated as undirected.

How It Works

To build a Cayley graph, list every element of the group as a vertex. For each vertex

g

and each generator

s \in S

, draw a directed edge from

g

gs

. Different generators are usually drawn in different colors. The resulting graph is always vertex-transitive, meaning it looks the same from every vertex — reflecting the symmetry of the group. Paths in the graph correspond to products of generators, so the graph distance between two elements equals the minimum number of generators needed to express one in terms of the other.

Worked Example

Problem: Construct the Cayley graph of the cyclic group

\mathbb{Z}_4 = \{0, 1, 2, 3\}

under addition modulo 4, with generating set

S = \{1\}

Step 1: List the vertices: one for each group element.

\text{Vertices: } 0,\; 1,\; 2,\; 3

Step 2: For the single generator

s = 1

, draw a directed edge from each element

g

g + 1 \pmod{4}

0 \to 1,\quad 1 \to 2,\quad 2 \to 3,\quad 3 \to 0

Step 3: The graph forms a directed cycle of length 4, which is the expected shape for a cyclic group with a single generator.

Answer: The Cayley graph

\text{Cay}(\mathbb{Z}_4, \{1\})

is a directed 4-cycle:

0 \to 1 \to 2 \to 3 \to 0

Why It Matters

Cayley graphs turn abstract algebraic relationships into geometric objects you can analyze visually. They appear in combinatorics, computer science (network design and routing algorithms), and geometric group theory, where the large-scale shape of a Cayley graph reveals deep properties of the underlying group.

Common Mistakes

Mistake: Including the identity element

e

in the generating set

S

, which adds a self-loop at every vertex.

Correction: By convention,

e \notin S

. Self-loops carry no structural information and are excluded from the standard definition.