The Petersen Graph’s Automorphism Group

A 2-Subset Model for the Petersen Graph

The Petersen graph has ten vertices and a large, highly structured collection of symmetries. To identify all of them, it helps to give its vertices a form that records the symmetry directly. Let \([5]=\{1,2,3,4,5\}\), and let \(V\) consist of all 2-element subsets of \([5]\). Two vertices are adjacent exactly when the corresponding subsets are disjoint. Thus a vertex such as \(12\) means the subset \(\{1,2\}\), not an edge of the graph.

There are \(\binom{5}{2}=10\) vertices. A vertex \(A\) has three neighbors: they are the 2-element subsets of the three elements outside \(A\). In particular, the graph is 3-regular. The model makes one set of symmetries immediate: any permutation of \([5]\) maps 2-subsets to 2-subsets and preserves disjointness. The main question is whether there are other automorphisms that do not arise this way.

An automorphism of a graph is a bijection from its vertex set to itself that preserves adjacency in both directions. The set of all automorphisms, with composition, is the automorphism group, denoted \(\operatorname{Aut}(G)\). For \(\sigma\in S_5\), define its induced map \(\rho(\sigma)\) on graph vertices by \(\rho(\sigma)(\{i,j\})=\{\sigma(i),\sigma(j)\}\). Because a bijection preserves whether two sets intersect, \(\rho(\sigma)\) is an automorphism. These induced maps give a group action of \(S_5\) on the Petersen graph.

Recognizing Five Canonical Independent Sets

An independent set is a set of vertices no two of which are adjacent. In this graph, that means a family of 2-subsets in which every two subsets intersect. For each \(i\in[5]\), define the star \(S_i=\{\{i,j\}:j\in[5],\ j\ne i\}\). Each \(S_i\) has four vertices, and any two of its members intersect at \(i\). Therefore each \(S_i\) is an independent set of size four.

Proof. Let \(\mathcal{F}\) be an independent set of size four, viewed as four distinct 2-subsets that intersect pairwise. Choose two distinct members of \(\mathcal{F}\). Since they intersect, they can be written as \(\{a,b\}\) and \(\{a,c\}\), where \(a,b,c\) are distinct. Any 2-subset that intersects both either contains \(a\) or is \(\{b,c\}\): if it does not contain \(a\), it must contain \(b\) to intersect \(\{a,b\}\) and \(c\) to intersect \(\{a,c\}\).

If \(\{b,c\}\in\mathcal{F}\), then no fourth distinct 2-subset can intersect all three of \(\{a,b\},\{a,c\},\{b,c\}\). Indeed, a 2-subset containing \(a\) must also contain \(b\) or \(c\) to meet \(\{b,c\}\), making it one of the first two sets; a 2-subset not containing \(a\) that meets the first two must be \(\{b,c\}\). This contradicts \(|\mathcal{F}|=4\). Therefore every member of \(\mathcal{F}\) contains \(a\), so \(\mathcal{F}\subseteq S_a\). Both sets have size four, hence \(\mathcal{F}=S_a\). \(\square\)

This lemma gives an intrinsic way to recognize the five stars using only the graph: they are exactly its independent sets of size four. An automorphism preserves adjacency and nonadjacency, so it sends independent sets to independent sets. Since it is a bijection, it also preserves their sizes. Consequently, every automorphism permutes the five stars.

Every Automorphism Comes from \(S_5\)

Proof. First, every \(\sigma\in S_5\) induces an automorphism \(\rho(\sigma)\), since \(\sigma\) is a bijection and hence preserves disjointness in both directions. The assignment \(\rho\) respects composition: applying \(\sigma\) and then \(\pi\) to a 2-subset has the same effect as applying \(\pi\circ\sigma\) (with the corresponding function-composition convention). Thus these induced maps form the natural group action.

Now let \(\varphi\) be any automorphism of the Petersen graph. By the lemma, \(\varphi\) permutes the five stars. Since the stars are distinct, there is a unique permutation \(\pi\in S_5\) such that \(\varphi(S_i)=S_{\pi(i)}\) for every \(i\in[5]\).

The vertex \(\{i,j\}\) is the unique member of \(S_i\cap S_j\). Since \(\varphi\) is a bijection, it maps this intersection to \(\varphi(S_i)\cap\varphi(S_j)=S_{\pi(i)}\cap S_{\pi(j)}\). The latter intersection consists of the single vertex \(\{\pi(i),\pi(j)\}\). Therefore \(\varphi(\{i,j\})=\{\pi(i),\pi(j)\}\) for every vertex \(\{i,j\}\). This proves that \(\varphi=\rho(\pi)\), so every automorphism is induced by an element of \(S_5\).

Finally, the inducing permutation is unique. If \(\rho(\pi)\) is the identity on graph vertices, then it fixes every star, because \(\rho(\pi)(S_i)=S_{\pi(i)}\). Distinctness of the stars gives \(S_{\pi(i)}=S_i\) only when \(\pi(i)=i\). This holds for all \(i\), so \(\pi\) is the identity. Hence the action is faithful as well as onto \(\operatorname{Aut}(G)\), and \(\operatorname{Aut}(G)\cong S_5\). \(\square\)

Why the Intrinsic Characterization Matters

The action of \(S_5\) on the vertices is evident from the subset model, but that observation alone only proves that the Petersen graph has at least those symmetries. The lemma supplies the missing upper bound: because the five stars can be recognized from the graph itself, every automorphism must permute them. Moreover, each graph vertex is recovered as the intersection of exactly two stars. Once the automorphism’s action on the stars is known, its action on every vertex is forced.

A common mistake is to confuse the size of a vertex orbit with the order of the automorphism group. For example, the orbit of \(12\) has size \(10\), but this does not imply that there are only ten automorphisms. The stabilizer has size \(12\), and orbit-stabilizer gives \(10\cdot12=120\), not \(10\). The orbit counts possible images of one vertex; it does not account for the different automorphisms that can have the same image of that vertex.