Why the Petersen Graph Is Not a Cayley Graph

The Petersen Graph and Its Symmetries

A graph can look highly symmetric without being a Cayley graph. Vertex-transitivity says that some automorphism can carry any chosen vertex to any other; it does not say that the automorphisms contain a subgroup that moves every vertex uniquely. The Petersen graph makes this distinction concrete: its automorphism group is \(S_5\), and it is vertex-transitive, but no subgroup of order 10 acts regularly on its vertices. We will prove that obstruction and use it to show that the Petersen graph is not a Cayley graph.

Let \([5]=\{1,2,3,4,5\}\). The Petersen graph \(P\) has as its vertices all 2-element subsets of \([5]\). Two vertices are adjacent exactly when the subsets are disjoint. For example, \(12\) denotes the subset \(\{1,2\}\), and \(12\) is adjacent to \(34\), but not to \(13\). Here graphs are finite, simple and undirected.

The equivalence follows from transitivity, which gives at least one such element, and trivial stabilizers, which ensure uniqueness: if \(h(u)=v=k(u)\), then \(k^{-1}h\) fixes \(u\), so \(h=k\). In particular, if a finite group acts regularly on a finite vertex set, its order equals the number of vertices.

Every permutation of \([5]\) takes 2-subsets to 2-subsets and preserves disjointness, so it gives an automorphism of \(P\). The automorphism-group result for the Petersen graph identifies its full automorphism group with \(S_5\) in this action. Since \(S_5\) can carry any 2-subset to any other, the Petersen graph is vertex-transitive. It has \(\binom{5}{2}=10\) vertices.

Cayley Graphs and Regular Actions

For a finite group \(\Gamma\) and a set \(S\subseteq \Gamma\setminus\{e\}\) satisfying \(S=S^{-1}\), the undirected Cayley graph \(\operatorname{Cay}(\Gamma,S)\) has vertex set \(\Gamma\), with \(x\) adjacent to \(y\) exactly when \(x^{-1}y\in S\). The condition \(S=S^{-1}\) makes adjacency symmetric, and \(e\notin S\) prevents loops.

Proof. First suppose \(G\) is isomorphic to \(\operatorname{Cay}(\Gamma,S)\). For any \(a\in\Gamma\), left multiplication \(x\mapsto ax\) preserves adjacency, because \((ax)^{-1}(ay)=x^{-1}y\). These permutations act transitively on \(\Gamma\), and the only left multiplication fixing \(x\) is multiplication by \(e\). Thus they form a regular subgroup of the automorphism group.

Conversely, suppose a subgroup \(H\leq\operatorname{Aut}(G)\) acts regularly on \(V(G)\). Choose a vertex \(v_0\), and define \(S=\{h\in H: v_0\text{ is adjacent to }h(v_0)\}\). The map \(h\mapsto h(v_0)\) is a bijection from \(H\) to \(V(G)\): regularity gives both existence and uniqueness of the element taking \(v_0\) to each vertex. The identity is not in \(S\), since \(G\) has no loops. Also \(S=S^{-1}\): if \(v_0\) is adjacent to \(h(v_0)\), applying \(h^{-1}\) shows that \(h^{-1}(v_0)\) is adjacent to \(v_0\), and the graph is undirected. Finally, \(h_1(v_0)\) and \(h_2(v_0)\) are adjacent exactly when \(v_0\) and \(h_1^{-1}h_2(v_0)\) are adjacent, because \(h_1^{-1}\) is an automorphism. That is exactly the Cayley adjacency rule. Hence \(G\) is isomorphic to \(\operatorname{Cay}(H,S)\). \(\square\)

For the Petersen graph, a regular subgroup would have to act on 10 vertices, so it would have order 10. The rest of the proof shows that every subgroup of order 10 in \(S_5\) has a nonidentity element fixing a vertex of \(P\), contradicting regularity.

What a Subgroup of Order 10 Must Look Like

We first establish the group structure needed for the argument. The details are included so that the obstruction does not depend on assuming a classification of subgroups of \(S_5\).

Proof. To see that \(H\) contains an element of order 5, consider the ordered 5-tuples \((g_1,g_2,g_3,g_4,g_5)\) of elements of \(H\) with \(g_1g_2g_3g_4g_5=e\). There are \(10^4\) such tuples, since the first four entries determine the fifth. Cyclic rotation preserves this set: if the product is \(e\), then \(g_2g_3g_4g_5g_1=g_1^{-1}eg_1=e\). Rotation has orbits of size 1 or 5. Its fixed tuples are exactly \((g,g,g,g,g)\) with \(g^5=e\). Since the total number of tuples is divisible by 5, the number of fixed tuples is divisible by 5 as well. The identity gives one fixed tuple, so there are at least five fixed tuples and at least one nonidentity \(g\) with \(g^5=e\). Its order is 5.

There is also an element of order 2 in \(H\). Among the nine nonidentity elements, any element not equal to its inverse can be paired with its distinct inverse. Nine is odd, so at least one nonidentity element equals its inverse; that element has order 2. Call it \(s\), and let \(r\) be the element of order 5 just found. The subgroup \(\langle r\rangle\) has order 5 and index 2 in \(H\), so it is normal: its left and right cosets outside it are both the unique other coset. Conjugation by \(s\) therefore sends \(r\) to \(r^k\) for some \(k\in\{1,2,3,4\}\). Applying conjugation by \(s\) twice gives \(r^{k^2}=r\), so \(k^2\equiv1\pmod 5\), and hence \(k=1\) or \(k=4\).

If \(k=1\), then \(r\) and \(s\) commute. Their cyclic subgroups intersect only in the identity, since their orders are 5 and 2. Consequently \(rs\) has order 10: \((rs)^j=e\) implies \(r^j=s^{-j}\), an element of that intersection, so both \(5\mid j\) and \(2\mid j\). But no permutation of five symbols has order 10. Indeed, the possible cycle lengths in a permutation of five symbols have least common multiple at most 6: the largest possibilities include a 5-cycle (order 5), a 4-cycle and a fixed point (order 4), or a 3-cycle and a disjoint transposition (order 6). Thus \(k\neq1\), leaving \(k=4\) and \(srs^{-1}=r^{-1}\). \(\square\)

This lemma says that every subgroup of order 10 in \(S_5\) has the noncommuting, dihedral form: it consists of the five powers of \(r\) and a coset obtained by multiplying them by \(s\). The key point for the graph is not just this group structure, but how the involution \(s\) acts on the 2-subsets.

Why No Order-10 Subgroup Acts Regularly

Let \(H\leq S_5\) have order 10, and take \(r,s\in H\) as in the lemma. Label the five symbols by the residues \(0,1,2,3,4\) modulo 5 so that \(r(i)=i+1\). The relation \(srs^{-1}=r^{-1}\) is equivalent to \(sr=r^{-1}s\). Therefore \(s(i+1)=s(i)-1\) for every residue \(i\), which gives \(s(i)=a-i\), where \(a=s(0)\).

The equation \(2i=a\pmod 5\) has exactly one solution, because 2 has a multiplicative inverse modulo 5. Thus \(s\) fixes one symbol. The other four symbols form two pairs exchanged by \(s\): if \(s(i)=j\) and \(i\neq j\), then \(s(j)=i\), since \(s^2\) is the identity. Each exchanged pair \(\{i,j\}\) is a vertex of the Petersen graph, and \(s\) fixes that vertex as a set. Since \(s\) has order 2, it is a nonidentity element fixing a vertex. The action of \(H\) on the Petersen graph is not regular.

Proof. If the Petersen graph were a Cayley graph, the regular-subgroup criterion would give a subgroup \(H\leq\operatorname{Aut}(P)=S_5\) acting regularly on its 10 vertices. A regular action on 10 vertices requires \(|H|=10\). But the argument above shows that every subgroup of order 10 in \(S_5\) contains an involution fixing a 2-subset, so none acts regularly. This contradiction proves that the Petersen graph is not a Cayley graph. \(\square\)

Common Pitfall: Vertex-Transitive Does Not Mean Cayley

A tempting but invalid calculation is: “The Petersen graph has 10 vertices and \(|S_5|=120\), with \(10\mid120\), so \(S_5\) contains a subgroup of order 10 that acts regularly.” Divisibility of a group’s order by 10 does not establish that it has a subgroup of order 10, and it does not establish that any such subgroup acts regularly. Even the explicit subgroup of order 10 in the example above fails: \(s\) fixes \(25\) and \(34\).

The distinction is between two strengths of symmetry. Vertex-transitivity requires that some automorphism carry one vertex to another, with the automorphism allowed to depend on the pair. Regularity requires a subgroup in which each such move is achieved by exactly one element. The full group \(S_5\) is transitive on the Petersen graph’s 2-subsets, while every possible order-10 subgroup has a nontrivial vertex stabilizer. That is why vertex-transitivity does not suffice to make the Petersen graph a Cayley graph.