Hamiltonian Path

Suppose I am planning a vacation to a country with seven major cities. I have frequent flier miles on an airline that doesn't have direct flights between every pair of cities, and I only want to visit each city exactly once. Given a list of pairs of cities which are connected by a flight, can I book a trip that accomplishes this feat? What if I want to start and end at the same city?

This general problem is known as the Hamiltonian path problem. (Starting and ending in the same place gives the Hamiltonian cycle problem.) It bears a resemblance to the problem of finding an Eulerian path or an Eulerian circuit, which in the above example would be planning a trip that takes every flight exactly once. While there are simple necessary and sufficient conditions on a graph that admits an Eulerian path or an Eulerian circuit, the problem of finding a Hamiltonian path, or determining whether one exists, is quite difficult in general. In fact, the problem of determining whether a Hamiltonian path or cycle exists on a given graph is NP-complete.

A Hamiltonian path is a traversal of a (finite) graph that touches each vertex exactly once. If the start and end of the path are neighbors (i.e. share a common edge), the path can be extended to a cycle called a Hamiltonian cycle.

A Hamiltonian cycle on the regular dodecahedron.

Consider a graph with \( 64 \) vertices in an \( 8 \times 8 \) grid, with each vertex corresponding to a square on a chessboard, where two vertices share an edge if and only if the corresponding squares are a knight's move away. Then a Hamiltonian cycle on the graph corresponds to a closed knight's tour on the chessboard. An example of a Hamiltonian cycle on the chessboard graph.

Since the problem of determining if there is a Hamiltonian path is equivalent to other very hard problems, it is too much to expect that there will be easy necessary and sufficient conditions for such a path to exist. Intuitively, a Hamiltonian path should exist if there are "enough" edges relative to the number of vertices, so many sufficient conditions give lower bounds on the number of edges. But they are not necessary: there will be examples of graphs with Hamiltonian paths or cycles that lie outside the bounds of these conditions.

A simple graph is a graph such that any two distinct vertices have at most one edge between them, and there are no loops (edges that start and end at the same vertex). \(_\square\)

The closure of a graph on \(n \) vertices is obtained as follows: find a pair of vertices without an edge between them such that the sum of their degrees is at least \( n \). Draw an edge between them. Continue until you cannot find any more such pairs. (Exercise: show that the process produces the same graph no matter which pairs are chosen in which order.) \(_\square\)

Dirac, 1952: A simple graph (one without multiple edges between any pair of vertices, and with no edges that begin and end with the same vertex) on \( n \) vertices has a Hamiltonian cycle if every vertex has degree at least \( n/2 \).

Ore, 1960: A graph on \(n\) vertices with the property that any two non-adjacent vertices have degrees summing to \( \ge n \) has a Hamiltonian cycle.

Bondy-Chvatal, 1972: A graph has a Hamiltonian cycle if and only if its closure has a Hamiltonian cycle. \(_\square\)

Note that Bondy-Chvatal implies Ore because the closure of a graph in Ore's theorem is the complete graph \( K_n \) where every pair of vertices is connected by an edge, and of course the complete graph on \( n \ge 3\) vertices has a Hamiltonian cycle.

And Ore implies Dirac because if every vertex has degree at least \( n/2 \), then any two non-adjacent vertices have degrees summing to \( \ge n \).

None of these theorems apply to, for instance, the cycle \( H\) on \( 6 \) vertices, in which every vertex has degree \( 2 \) and the closure of \( H \) equals \( H \):