18Hamilton CyclesContentsTOUGHGRAPHS+HYPOHAMILTON18.2 NonhamilttonianPlanarGraphsBERG'ST+++++..++BARNETTE'S CONJE18.3 Path and Cycle ExchangePATHEXCHANGECYCLE EXCHANGESDIRAC'S THEOREMTHE CLOSURE OF A GRAPHTHE CHVATAL-ERDOSTHEOREM18.4 Path Exchanges and ParityTHELOLLIPOPLEMMAUNIQUELY HAMILTONIAN GRAPHSSHEEHAN'S CONJECTURE18.5 HamiCyclesinRm Graphs......OSAOSR18.6 Related Reading.BRIDGETHE HOPPING LEMLONG PATHS AND CYCLES18.1 Hamiltonian and Nonhamiltonian GraphsRecall that a path or cycle which contains every vertex of a graph is called aHamiltonpathor Hamiltoncycleof thegraph.Suchpathsand cycles arenamecafterSirWilliamRowanHamilton,whodescribed,inalettertohisfriendGravesin 1856, a mathematical game on the dodecahedron (Figure 18.la) in which one18 Hamilton Cycles Contents 18.1 Hamiltonian and Nonhamiltonian Graphs . . . . . . . . . . 471 Tough Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472 Hypohamiltonian Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473 18.2 Nonhamiltonian Planar Graphs . . . . . . . . . . . . . . . . . . . . 478 Grinberg’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 Barnette’s Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 18.3 Path and Cycle Exchanges . . . . . . . . . . . . . . . . . . . . . . . . 483 Path Exchanges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 Cycle Exchanges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 Dirac’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 The Closure of a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 The Chvatal–Erd ´ os Theorem ˝ . . . . . . . . . . . . . . . . . . . . . . . . 488 18.4 Path Exchanges and Parity . . . . . . . . . . . . . . . . . . . . . . . . 492 The Lollipop Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 Uniquely Hamiltonian Graphs . . . . . . . . . . . . . . . . . . . . . . . 494 Sheehan’s Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 18.5 Hamilton Cycles in Random Graphs . . . . . . . . . . . . . . . 499 Posa’s Lemma ´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499 18.6 Related Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 The Bridge Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 The Hopping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 Long Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 18.1 Hamiltonian and Nonhamiltonian Graphs Recall that a path or cycle which contains every vertex of a graph is called a Hamilton path or Hamilton cycle of the graph. Such paths and cycles are named after Sir William Rowan Hamilton, who described, in a letter to his friend Graves in 1856, a mathematical game on the dodecahedron (Figure 18.1a) in which one