The Petersen Graph Is Hypohamiltonian

Hamiltonian After Every Vertex Deletion

A graph can fail to have a Hamiltonian cycle and still be remarkably close to having one: removing any single vertex may leave a graph with a Hamiltonian cycle. The Petersen graph is a standard example. Its symmetry makes the deletion claim manageable, but the claim that the original graph is not Hamiltonian requires a separate argument. We will prove both parts using a model whose vertices are pairs.

Thus, hypohamiltonicity has two distinct requirements. Showing that one vertex deletion leaves a Hamiltonian graph is not enough; we must establish the deletion property for every vertex and also show that the original graph has no Hamiltonian cycle.

The Petersen Graph as Disjoint Pairs

Let \(S=\{1,2,3,4,5\}\). The Petersen graph \(P\) has one vertex for each 2-element subset of \(S\), and two distinct vertices are adjacent exactly when their corresponding subsets are disjoint. This defines a finite simple graph. For example, \(12\) denotes the vertex \(\{1,2\}\), and \(12\) is adjacent to \(34\) because \(\{1,2\}\cap\{3,4\}=\varnothing\).

There are ten vertices, since there are \(\binom{5}{2}=10\) choices of a 2-element subset. Each vertex has three neighbors: once its two elements are chosen, the other three elements of \(S\) remain, and any 2-element subset of those three gives a disjoint vertex. The graph therefore has degree three at every vertex.

It is useful to organize the ten labels into two groups. Indices below are taken modulo \(5\), and the entries in the table are 2-subsets, not additional vertices.

The outer edges are \(O_iO_{i+1}\), the inner edges are \(I_iI_{i+2}\), and the spokes are \(O_iI_i\), for \(i=0,1,2,3,4\). Each listed edge joins disjoint pairs. These are fifteen distinct edges; since each of the ten vertices has degree three, the degree sum is \(10\cdot3=30\), so the handshake lemma gives \(30/2=15\) edges in total. Thus the listed outer edges, inner edges and spokes account for every edge of \(P\).

Symmetry of the 2-Subset Model

Proof. Regard \(A\) and \(B\) as 2-element subsets of \(S\). Choose a bijection from the two elements of \(A\) to the two elements of \(B\), and a bijection from the three elements of \(S\setminus A\) to the three elements of \(S\setminus B\). Together these give a permutation \(\pi\) of \(S\) with \(\pi(A)=B\). Apply \(\pi\) to every 2-subset. Two subsets are disjoint exactly when their images are disjoint, because a bijection preserves intersections and disjointness. Therefore this relabelling preserves adjacency and is an automorphism of \(P\). \(\square\)

This symmetry reduces the deletion claim to one explicit construction. If a Hamiltonian cycle is found after deleting one vertex, an automorphism taking that vertex to any other vertex carries the cycle to a Hamiltonian cycle after that other vertex is deleted.

A Nine-Vertex Cycle

The examples illustrate the general argument: the proposition supplies a relabelling taking \(12\) to any chosen vertex, and relabelling the displayed nine-cycle gives a Hamiltonian cycle after that vertex is deleted. It remains to prove that \(P\) itself is not Hamiltonian.

Why the Petersen Graph Is Not Hamiltonian

We count how many spokes a hypothetical Hamiltonian cycle could use. The count is effective because each vertex of \(P\) has degree three, while a cycle uses exactly two incident edges at each of its vertices.

Proof. Suppose that \(C\) is a Hamiltonian cycle of \(P\), and let \(k\) be the number of spokes \(O_iI_i\) used by \(C\). The five outer vertices have total degree \(10\) within \(C\). If \(a\) outer-cycle edges are used, their contribution to this degree total is \(2a\), and the used spokes contribute \(k\). Consequently \(2a+k=10\), so \(k\) is even. The same count applies to the inner vertices. Since there are only five spokes, the possibilities are \(k=0,2,4\).

If \(k=0\), every outer vertex must use both of its outer-cycle edges, so all five outer edges belong to \(C\). The same reasoning puts all five inner edges in \(C\). These two cycles are disjoint, contradicting the fact that \(C\) is one cycle containing all ten vertices.

If \(k=2\), the two indices of the used spokes are the same in the outer and inner layers. In each layer, the two spoke endpoints must each use one edge within that layer, while the other three vertices use two layer edges each. In a 5-cycle this means that exactly one layer edge is omitted: the endpoints of the omitted edge are the two vertices with only one selected layer edge. Thus the two spoke indices must be adjacent in the outer cycle and adjacent in the inner cycle. But outer adjacency means that their indices differ by \(1\) or \(-1\) modulo \(5\), whereas inner adjacency means that they differ by \(2\) or \(-2\) modulo \(5\). No pair of indices satisfies both conditions. Hence \(k\ne2\).

If \(k=4\), let \(j\) be the index of the unused spoke. In each layer, the vertex with index \(j\) must use both of its layer edges, while each other vertex must use exactly one layer edge. In the outer cycle these selected edges are \(O_jO_{j+1}\), \(O_jO_{j-1}\), and the edge between the two remaining vertices \(O_{j+2}\) and \(O_{j-2}\). In the inner cycle they are \(I_jI_{j+2}\), \(I_jI_{j-2}\), and the edge \(I_{j+1}I_{j-1}\). The description follows from the required degrees: the two neighbors of \(j\) must each receive their one layer edge from \(j\), and the two remaining vertices must be joined to each other.

Rotate the indices so that \(j=0\). The selected layer edges are then \(O_0O_1,O_0O_4,O_2O_3\) and \(I_0I_2,I_0I_3,I_1I_4\), together with the four used spokes at indices \(1,2,3,4\). These edges form two separate 5-cycles: \(O_0,O_1,I_1,I_4,O_4,O_0\) and \(O_2,O_3,I_3,I_0,I_2,O_2\). Their union is disconnected, so it cannot be the single Hamiltonian cycle \(C\). Thus \(k\ne4\).

All possible even values of \(k\) have now been ruled out. This contradicts the assumption that \(C\) exists, proving that the Petersen graph is not Hamiltonian. \(\square\)

The Hypohamiltonian Conclusion

Proof. The preceding theorem shows that \(P\) is not Hamiltonian. The nine-cycle displayed for \(P-12\) shows that this vertex deletion is Hamiltonian. For any vertex \(v\) of \(P\), vertex-transitivity gives an automorphism taking \(12\) to \(v\). The image of the nine-cycle is then a cycle through every vertex of \(P-v\) exactly once, so \(P-v\) is Hamiltonian. Both requirements in the definition of hypohamiltonicity hold. \(\square\)

A Common Pitfall

A nine-cycle in \(P-12\) does not show that \(P\) has a Hamiltonian cycle. One cannot obtain a cycle containing \(12\) merely by appending \(12\) to the nine-cycle: a cycle must return to its start through edges, and inserting a vertex requires replacing an existing edge by two edges incident with that vertex. In the displayed nine-cycle, the neighbors of \(12\) in \(P\) are \(34,35,45\), and no two of those labels are consecutive on the displayed cycle. More importantly, even a different deletion cycle would not by itself prove that the original graph is non-Hamiltonian. The spoke-counting argument is what rules out a Hamiltonian cycle in \(P\); vertex-transitivity is what extends the one explicit deletion cycle to every vertex.