A bipartite regular graph
A path is called Hamiltonian if it traverses every vertex exactly once. A circuit is called Hamiltonian if it traverses every vertex exactly once, except that the initial and final vertices are the same. The definition is similar to that of Eulerian trails and circuits, but the question of whether a graph has a Hamiltonian path or circuit turns out to be much more difficult to answer than the question of whether it has an Eulerian trail or circuit.
Some information is easy to obtain. \({ K _ n }\) always has a Hamiltonian path and a Hamiltonian circuit. We can order the vertices however we like and then visit each one in order, since every pair of vertices is connected by an edge. To get a circuit we just append another edge from the last vertex in the path to the first.
For \({ K _ { p , q } }\) the answer depends on \({ p }\) and \({ q }\). Any walk in \({ K _ { p , q } }\) alternately visits vertices from the set of \({ p }\) vertices and the set of \({ q }\) vertices, since there are no edges within either set. So at the end of any path in \({ K _ { p , q } }\) the number of edges visited from one set differs by at most one from the number visited from the other set. So there is no Hamiltonian path unless \({ | p - q | ≤ 1 }\). Conversely, if this inequality is satisfied then we can find a Hamiltonian path. If \({ p = q }\) then we can also find a Hamiltonian circuit.
The bipartite regular graph we used earlier as an example for Eulerian paths also has a Hamiltonian circuit, which is just a, b, c, d, e, f, g, h, i, j, k, l, a, which is shown in the accompanying diagram.
This Hamiltonian path is far from unique. We can obtain other ones just by visiting the vertices in clockwise or anticlockwise order.
The earliest example of a Hamiltonian path is the Knight’s Tour problem in chess. The graph in question has the squares of the chessboard as vertices and vertices are adjacent if and only if they are a knight’s move apart. A knight’s tour is a set of moves visiting each square exactly once, i.e. a Hamiltonian path in the graph. The earliest known solutions are by al-Adli ar-Rumi and by Rudrata, and date to the ninth century. Again, these Hamiltonian paths are far from unique. In fact there are 19,591,828,170,979,904 of them.