The Regular-Subgroup Criterion for Cayley Graphs

From Graph Symmetry to a Group Description

A Cayley graph starts with a group and records selected differences between its elements as edges. The regular-subgroup criterion reverses this construction: it identifies exactly when a graph’s symmetries allow its vertices to be treated as group elements in a way that makes adjacency depend only on group differences. The key requirement is not merely that the graph has many symmetries. A subgroup must act both transitively and without nonidentity elements fixing vertices.

All graphs in this tutorial are finite and simple. An automorphism of a graph \(G\) is a permutation of \(V(G)\) that preserves adjacency in both directions; the automorphisms form a group under composition, denoted \(\operatorname{Aut}(G)\). A group action of \(H\) on \(V(G)\) assigns to each \(h\in H\) a permutation \(v\mapsto h(v)\), compatibly with the group operation. Here the groups and vertex sets under discussion are finite.

For a group \(\Gamma\), write its identity as \(e\). A subset \(S\subseteq\Gamma\) is inverse-closed if \(s^{-1}\in S\) whenever \(s\in S\). The standard undirected Cayley graph \(\operatorname{Cay}(\Gamma,S)\) has vertex set \(\Gamma\), with distinct vertices \(x,y\) adjacent exactly when \(x^{-1}y\in S\). We require \(e\notin S\) to avoid loops and \(S\) inverse-closed to make adjacency symmetric. The generating set need not generate \(\Gamma\); the Cayley graph is allowed to be disconnected.

Why Regularity Gives Group Coordinates

The mechanism behind the criterion is that a regular action gives each vertex a unique group label. Fixing one vertex \(v_0\), label the vertex \(h(v_0)\) by \(h\). Transitivity ensures that every vertex receives a label, and freeness ensures that no two elements receive the same label. Under these labels, adjacency can be tested by moving one endpoint back to \(v_0\).

Proof. For any \(x\in X\), transitivity gives an \(h\in H\) with \(h(x_0)=x\), so the map is surjective. Suppose \(h_1(x_0)=h_2(x_0)\). The action law gives \((h_2^{-1}h_1)(x_0)=x_0\). Freeness implies \(h_2^{-1}h_1=e\), hence \(h_1=h_2\); the map is injective. \(\square\)

Proof of the theorem. First suppose that \(G\) is isomorphic to \(\operatorname{Cay}(\Gamma,S)\), where \(S\) satisfies the conditions above. For each \(a\in\Gamma\), define the left translation \(L_a(x)=ax\). For any \(x,y\in\Gamma\),

Thus \(x\) and \(y\) are adjacent exactly when \(ax\) and \(ay\) are adjacent, so every \(L_a\) is a graph automorphism. The translations form a subgroup: \(L_aL_b=L_{ab}\) and \(L_a^{-1}=L_{a^{-1}}\). This subgroup acts regularly on \(\Gamma\), because for any \(x,y\in\Gamma\), the unique left translation taking \(x\) to \(y\) is \(L_{yx^{-1}}\). Transporting these automorphisms through the graph isomorphism gives a regular subgroup of \(\operatorname{Aut}(G)\).

Conversely, suppose \(V(G)\ne\varnothing\) and \(H\leq\operatorname{Aut}(G)\) acts regularly on \(V(G)\). Fix \(v_0\in V(G)\), and define

The identity is not in \(S\), since a simple graph has no loop at \(v_0\). Also \(S\) is inverse-closed. Indeed, if \(h\in S\), then applying the automorphism \(h^{-1}\) to the edge between \(v_0\) and \(h(v_0)\) gives an edge between \(h^{-1}(v_0)\) and \(v_0\). Since edges are undirected, this says \(h^{-1}\in S\).

By the lemma, the map \(\phi:H\to V(G)\) defined by \(\phi(h)=h(v_0)\) is a bijection. For \(a,b\in H\), applying the automorphism \(a^{-1}\) shows that \(a(v_0)\) and \(b(v_0)\) are adjacent exactly when \(v_0\) and \((a^{-1}b)(v_0)\) are adjacent. By the definition of \(S\), this is equivalent to \(a^{-1}b\in S\). Therefore \(\phi\) preserves adjacency in both directions and is an isomorphism from \(\operatorname{Cay}(H,S)\) to \(G\). This proves the reverse implication. \(\square\)

The nonempty-vertex hypothesis matters. A group always has an identity, so every Cayley graph has at least one vertex. On the empty set, transitivity and freeness could both hold vacuously under some definitions of action, but the empty graph cannot be isomorphic to a Cayley graph. The theorem therefore excludes it.

Worked Constructions

What the Criterion Does—and Does Not—Say

The theorem concerns the existence of a regular subgroup, not whether the entire automorphism group acts regularly. For \(K_3\), every permutation is an automorphism, so \(\operatorname{Aut}(K_3)\) has \(3!=6\) elements. A regular action on three vertices must have exactly three elements: fixing one vertex, the map from group elements to its images must be a bijection. Thus the full automorphism group is not regular here, even though the subgroup \(\{e,r,r^2\}\) is.

This distinction also separates regularity from transitivity. Transitivity says that some symmetry can carry any chosen vertex to any other; it does not say that the symmetries form a group with a unique element carrying one vertex to another. The criterion requires the stronger, regular action of a subgroup.

When searching for a Cayley representation, the proof provides a direct construction. Choose a regular subgroup \(H\), choose a base vertex \(v_0\), and collect the elements of \(H\) that take \(v_0\) to its neighbors. That set is the Cayley connection set. Its definition ensures the correct edges at the base vertex; applying the group action then ensures the correct adjacency rule everywhere.

Common pitfall. It is incorrect to define a regular action as simply a transitive action. For example, the full permutation group on the three vertices of \(K_3\) is transitive, but it has six elements, not three. A regular action on a three-element set must have exactly three group elements, as follows from the bijection in the lemma. The correction is to test both transitivity and freeness, or equivalently to check that for every ordered pair of vertices there is exactly one group element carrying the first to the second. Also check that the graph has at least one vertex before applying the criterion.