Hamiltonian Paths and Cycles
Sir William Rowan Hamilton was an Irish mathematician and the inventor of icosian calculus — which he used to investigate closed edge paths on a dodecahedron that visit each vertex exactly once (also called Hamiltonian paths!). While it won’t be possible to even touch upon icosian calculus in a single post, let’s try and understand Hamiltonian paths and cycles in the more general context of a graph — not necessarily a dodecahedron.
In our previous post on the Seven Bridges of Königsberg, we encountered the definition of a walk in a graph — i.e. a sequence of alternating vertices and edges. In particular, a path is a walk in which all vertices and edges are distinct. Building on that, a Hamiltonian path is a path in a graph that visits each vertex exactly once.
In the graph shown above, 4 -> 3 -> 1 -> 6 is a path, since it is composed of distinct vertices and edges. Can we find Hamiltonian paths too? Yes!
2 -> 6 -> 5 -> 1 -> 3 -> 4 is one of them!
A graph that contains a Hamiltonian path is called a traceable graph. The Herschel graph, named after British astronomer Alexander Stewart Herschel, is traceable. Finding a Hamiltonian path has been left as an exercise for the reader.
Naturally, we can extend the concept of Hamiltonian paths to cycles — a cycle that visits each vertex exactly once is called a Hamiltonian cycle, and a graph that contains such a cycle is called a Hamiltonian graph.
Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to a Hamiltonian cycle only if its endpoints are adjacent.
Interestingly enough, the graphs of all platonic solids (there are only five) are Hamiltonian — the dodecahedron (shown alongside) being one of them. As a fun exercise, try finding Hamiltonian cycles in the other four platonic graphs!
Hamiltonian paths come up often in board game theory too — chess, for example. If you model each square on the 8x8 board as a vertex of a graph and consider finding a sequence of moves for a knight such that the knight visits every square (vertex) exactly once, what do you get? The knight’s tour problem!
To conclude, here’s a thought-provoking problem for you — show (mathematically, of course) that the Petersen graph has no Hamiltonian cycle. In fact, it is worth mentioning that the Petersen graph is hypohamiltonian, i.e. deleting any vertex from it makes it Hamiltonian.
Read more:
1. A Study of Sufficient Conditions for Hamiltonian Cycles (Rose-Hulman Undergraduate Math Journal)
2. NP-completeness of Hamiltonian Paths and Cycles
3. The Knight’s Tour Problem
4. Knight’s Tours and Zeta Functions
