ABSTRACT
AHamiltonian cycle is a spanning cycle in a graph (a cycle through every vertex). Introduced by Kirkman in 1855, Hamiltonian cycles are named for Sir William Hamilton, who described a game on the graph of the dodecahedron, in which one player would specify a 5-vertex path and the other would have to extend it to a cycle. The game was marketed as the Traveler’s Dodecahedron, a wooden version, in which the vertices were named for 20 important cities. Here, we use a, b, c, . . . , t to represent these vertices as illustrated in Figure 9.1. It was not commercially successful.
