The Petersen Graph and Its Spokes
The Petersen graph is a useful example of a graph that satisfies several familiar conditions for Hamiltonicity but nevertheless has no Hamiltonian cycle. A direct proof can be organized around its five edges joining an outer cycle to an inner cycle. These joining edges are called spokes. The key is that a Hamiltonian cycle cannot use an arbitrary number of spokes: the structure of the two 5-cycles forces only three possible counts, and each count can be analyzed completely.
All graphs in this tutorial are finite and simple. A cycle is a closed sequence of at least three edges whose vertices, apart from the repeated starting vertex, are distinct. A cycle is Hamiltonian if it contains every vertex of the graph exactly once. Thus, at each vertex of a Hamiltonian cycle, exactly two of the graph’s edges are used.
This definition gives \(5+5+5=15\) edges: five outer edges, five inner edges and five spokes. The outer and inner cycles are disjoint, and the spokes are the only edges joining their vertex sets. We will call the two sets of cycle edges the outer edges and inner edges, respectively.
Which Spoke Counts Are Possible?
Suppose a Hamiltonian cycle \(C\) is present. As we travel around \(C\), every use of a spoke moves between the set of outer vertices and the set of inner vertices. The cycle must return to its starting side. Each move from outer to inner must therefore be matched by a move from inner to outer. Consequently, the number of spokes in \(C\) is even. There are only five spokes in \(G\), so the possible counts are \(0\), \(2\), and \(4\).
At any vertex, the Hamiltonian cycle uses exactly two incident edges. If a spoke at that vertex is not used, both used edges must lie in that vertex’s 5-cycle. If its spoke is used, exactly one used edge must lie in that 5-cycle. These degree requirements will determine the selected edges in each case.
Proof. Assume, for contradiction, that \(C\) is a Hamiltonian cycle in \(G\). By the parity argument, \(C\) uses \(0\), \(2\), or \(4\) spokes. We show that none of these cases can give a Hamiltonian cycle.
Case 1: zero spokes. Every vertex must then use both of its edges from its own 5-cycle. Therefore all five outer edges and all five inner edges are in \(C\). Those ten edges form two separate 5-cycles, with no selected edge connecting them. Their union is not a single cycle, so it is not Hamiltonian.
Case 2: two spokes. Suppose the selected spokes are \(u_i v_i\) and \(u_j v_j\), where \(i\ne j\). In the outer 5-cycle, the vertices \(u_i\) and \(u_j\) each need exactly one selected outer edge; the other three outer vertices each need two. The sum of these required outer degrees is \(1+1+2+2+2=8\), so exactly \(8/2=4\) outer edges must be selected. Of the five outer edges, exactly one is omitted. Its endpoints are precisely the vertices with selected outer degree one, namely \(u_i\) and \(u_j\). Hence \(u_i\) and \(u_j\) must be adjacent on the outer cycle, which means \(j-i\equiv 1\) or \(-1\pmod 5\).
The same degree count applies to the inner 5-cycle: exactly four inner edges must be selected, and the omitted edge must join \(v_i\) to \(v_j\). In the inner cycle, vertices \(v_i\) and \(v_j\) are adjacent only if \(j-i\equiv 2\) or \(-2\pmod 5\). No difference modulo \(5\) is both \(\pm1\) and \(\pm2\). The two spokes therefore cannot satisfy both required adjacency conditions.
Case 3: four spokes. Since there are five spokes, exactly one is omitted. Write it as \(u_kv_k\). The vertices \(u_k\) and \(v_k\) each need two selected edges from their respective 5-cycles; the other four vertices on each side each need one. Consider any 5-cycle written in order as \(w_0,w_1,w_2,w_3,w_4,w_0\), with \(w_0\) the vertex needing two selected cycle edges. The edges \(w_4w_0\) and \(w_0w_1\) are forced. Since \(w_1\) then needs no more selected edge, \(w_1w_2\) is omitted. Thus \(w_2w_3\) must be selected, and \(w_3w_4\) is omitted because \(w_4\) already has its required selected edge. The selected edges on this 5-cycle are exactly \(w_4w_0,w_0w_1,w_2w_3\).
Apply that pattern first to the outer order \(u_k,u_{k+1},u_{k+2},u_{k+3},u_{k+4}\), and then to the inner order \(v_k,v_{k+2},v_{k+4},v_{k+1},v_{k+3}\). The selected outer edges must be \(u_{k-1}u_k,u_ku_{k+1},u_{k+2}u_{k+3}\). The selected inner edges must be \(v_kv_{k+2},v_kv_{k+3},v_{k+4}v_{k+1}\). The four selected spokes are all \(u_i v_i\) with \(i\ne k\).
These selected edges form two disjoint 5-cycles. One is \(u_{k-1},u_k,u_{k+1},v_{k+1},v_{k-1},u_{k-1}\): its outer path has two edges, its two spokes are selected, and \(v_{k+1}v_{k-1}=v_{k+1}v_{k+4}\) is the selected inner edge. The other is \(u_{k+2},u_{k+3},v_{k+3},v_k,v_{k+2},u_{k+2}\): it uses the selected outer edge, two selected spokes, and the inner path through \(v_k\). The cycles are disjoint and together contain all ten vertices. Their union is not one Hamiltonian cycle. This rules out the four-spoke case as well.
All possible spoke counts have led to a contradiction. Therefore the Petersen graph has no Hamiltonian cycle. \(\square\)
Worked Cases
Worked Example: No Spokes
Use the Petersen graph \(G=(V,E)\) defined above. Suppose a proposed Hamiltonian cycle uses no spokes. At each \(u_i\), both outer edges \(u_{i-1}u_i\) and \(u_iu_{i+1}\) must be selected. As \(i\) ranges from \(0\) to \(4\), this selects the outer edges \(u_0u_1,u_1u_2,u_2u_3,u_3u_4,u_4u_0\). At each \(v_i\), both inner edges must likewise be selected, giving \(v_0v_2,v_2v_4,v_4v_1,v_1v_3,v_3v_0\).
Check: There are \(5+5=10\) selected edges, and every vertex has selected degree two. But the selected edges form the outer 5-cycle and the inner 5-cycle separately; there is no selected edge between them. Thus the selected subgraph has two components, whereas a Hamiltonian cycle must be connected.
Worked Example: Two Candidate Spokes
Again use the explicitly defined Petersen graph \(G=(V,E)\). Try selecting the spokes \(u_0v_0\) and \(u_1v_1\). The outer endpoints \(u_0,u_1\) each need one selected outer edge, while \(u_2,u_3,u_4\) each need two. The outer required degree sum is \(1+1+2+2+2=8\), giving \(8/2=4\) selected outer edges. The one omitted outer edge must join \(u_0\) to \(u_1\), so this side is consistent: omit \(u_0u_1\).
On the inner side, the required degree sum is also \(8\), so exactly four inner edges would have to be selected. The omitted edge must join \(v_0\) to \(v_1\). But the inner edges are \(v_0v_2,v_1v_3,v_2v_4,v_3v_0,v_4v_1\); none is \(v_0v_1\). The required omitted edge does not exist, so this spoke choice cannot be part of a Hamiltonian cycle.
Check: The outer cycle has five edges and four are retained, as required by the degree sum. The inner cycle also has five edges, but its endpoints \(v_0,v_1\) are not adjacent in that cycle. This is the specific obstruction for these two spokes.
Worked Example: Four Spokes Split into Two 5-Cycles
Use \(G=(V,E)\) as defined above and omit the spoke \(u_0v_0\). The outer order is \(u_0,u_1,u_2,u_3,u_4\), so the selected outer edges are \(u_4u_0,u_0u_1,u_2u_3\). The inner order is \(v_0,v_2,v_4,v_1,v_3\), so the selected inner edges are \(v_0v_2,v_0v_3,v_4v_1\). The selected spokes are \(u_1v_1,u_2v_2,u_3v_3,u_4v_4\).
The edges form the cycles \(u_4,u_0,u_1,v_1,v_4,u_4\) and \(u_2,u_3,v_3,v_0,v_2,u_2\). Each has five edges. Their vertex sets are disjoint: the first uses \(u_4,u_0,u_1,v_1,v_4\), and the second uses \(u_2,u_3,v_3,v_0,v_2\).
Check: The selected edge count is \(3+3+4=10\), matching the sum of the two cycle lengths, \(5+5=10\). The two cycles cover all ten vertices, but because they are disjoint they do not form a single Hamiltonian cycle.
A Common Counting Pitfall
Wrong calculation: “There are five spokes, so a Hamiltonian cycle must use all five.” This confuses the number of available spokes with the number a cycle uses. A cycle crossing from the outer vertices to the inner vertices must also cross back; its number of crossings is even. In particular, five spokes cannot belong to a Hamiltonian cycle. The correct possible counts are \(0\), \(2\), and \(4\), and the proof must rule out each one. The four-spoke case is not excluded by parity alone: its selected edges do satisfy the degree requirement, but they split into two separate cycles.
The proof’s structure is useful beyond this particular graph. When a graph is built from two vertex sets joined by a small set of edges, count how often a proposed cycle crosses between the sets. Then use the degree-two condition at each vertex to determine what the cycle must do inside each part. Here, that local information is strong enough to settle all cases without searching through every possible cycle.
Check Your Understanding
Use the spoke model and the degree conditions from the proof to answer these questions.
- Why must a cycle use an even number of spokes when the vertices are divided into the outer and inner sets?
- In the two-spoke case, why does the omitted edge on each 5-cycle have to join the two vertices incident with selected spokes?
- Which differences of indices describe adjacent vertices in the outer cycle, and which describe adjacent vertices in the inner cycle?
- If the omitted spoke is \(u_3v_3\), write down the three selected outer edges and the three selected inner edges forced by the four-spoke case.
- Why does a union of two disjoint cycles covering every vertex still fail to be a Hamiltonian cycle?