Hamilton cycle

A Hamilton cycle, also called a Hamiltonian cycle, is a cycle in a graph containing every vertex of the graph. Here the convention is a finite simple graph whose edges are undirected, with $n=|V|\ge 3$. A traversal is a sequencewhere $v_0,\dots ,v_{n-1}$ are all the distinct vertices and $\{v_i,v_{i+1}\}\in E$ for $0\le i<n$. Thus "once" means once before the closing return: the start appears again at the end, and there are exactly $n$ traversed edges. The graph may contain additional unused edges.^[ref]

A Hamiltonian path visits all vertices once without requiring a return. Removing an edge from a Hamilton cycle gives a Hamiltonian path; a particular Hamiltonian path closes only if its endpoints are adjacent. An Euler circuit instead traverses every edge exactly once and can revisit vertices midway. The two requirements are independent, as these original labelled examples show.

For the complete graph $K_4$, use $V=\{A,B,C,D\}$ and $E=\{AB,AC,AD,BC,BD,CD\}$, where $AB$ abbreviates the unordered pair $\{A,B\}$. The route $A,B,C,D,A$ is a Hamilton cycle: it visits every vertex and uses four of the six edges, omitting $AC$ and $BD$. It is not an Euler circuit, and the graph admits no Euler circuit at all: every vertex degree is three, contradicting the Euler circuit criterion. The crossing of the drawn diagonals is not another vertex.

Conversely, take two triangles in a graph sharing only $X$, with $V=\{X,A,B,C,D\}$ and $E=\{XA,AB,BX,XC,CD,DX\}$. The route $X,A,B,X,C,D,X$ is an Euler circuit, using all six edges once; the vertex degrees are $4,2,2,2,2$. It cannot be a Hamilton cycle, since $X$ occurs midway as well as at the start and end. More strongly, no Hamilton cycle exists: $X$ is a cut vertex, and deleting it leaves the two separate edges $AB$ and $CD$. Nevertheless, $A,B,X,C,D$ is a Hamiltonian path, whose endpoints are not adjacent.

A Hamiltonian graph is a graph containing a Hamilton cycle. This describes existence of a spanning graph cycle, rather than requiring every edge of the graph to belong to that graph cycle. In the finite simple graph convention, $K_n$ is a Hamiltonian graph for $n\ge 3$, because any ordering of its vertices closes using available edges.

A Hamiltonian graph must be a connected graph and have minimum degree $\delta (G)\ge 2$: each vertex has two distinct neighbours on its Hamilton cycle. It also has no cut vertex. Indeed, deleting any vertex from the Hamilton cycle leaves a graph path through every remaining vertex, so the remaining graph is connected. These are quick ways to rule out a Hamilton cycle.^[ref]

Even these conditions together are not sufficient: the complete bipartite graph $K_{2,3}$ is connected, has minimum degree two and no cut vertex, but has no Hamilton cycle. Every graph cycle in a bipartite graph alternates between its two parts, using equally many vertices from each; it cannot use all two and all three.

In the other direction, Dirac's theorem gives a sufficient condition: a finite simple graph with $n\ge 3$ and $\delta (G)\ge n/2$ has a Hamilton cycle. Failure of this inequality proves nothing by itself: the cycle graph $C_5$ has a Hamilton cycle despite $\delta (C_5)=2<5/2$.^[ref]

A weighted Hamilton cycle is a Hamilton cycle in a weighted graph, with cost equal to the sum of its traversed edge weights. Here weights represent symmetric nonnegative costs, rather than conductances. Asking whether a Hamilton cycle exists is a feasibility question; asking for the cheapest one is an instance of the travelling salesman problem. A complete graph supplies every possible connection between distinct vertices, making feasibility automatic for $n\ge 3$, while choosing the cheapest visiting order remains a separate mathematical optimization problem.

Assign the complete graph $K_4$ the symmetric edge costs $w_{AB}=2$, $w_{BC}=3$, $w_{CD}=4$, $w_{AD}=5$, $w_{AC}=6$ and $w_{BD}=7$, in arbitrary units. Fix the start at $A$ and identify each Hamilton cycle with its reverse. The three possibilities areThese exhaust the possibilities: the permutations of the other three vertices give $3!=6$ orders, paired into three reversals. Hence the perimeter tour really is optimal for this toy instance. The diagram's geometric lengths are not costs, and no triangle inequality is assumed.

The usefulness of this model is to distinguish visiting required sites from covering required connections. If tasks are assigned to vertices and the route must return after one visit to each, a weighted Hamilton cycle captures the ordering requirement. If the job instead requires each edge once, the relevant object is an Euler circuit. The shortest path problem asks only for a cheapest route between specified endpoints. A 1954 primary research paper gave a concrete motivation for the travelling salesman problem: certify that a particular tour through 49 cities has minimum road-distance cost.^[ref]

These are abstract route models. If a cost stands for a whole graph path through an underlying network, travelling between consecutive task vertices can pass through intermediate network vertices more than once. One visit per task therefore does not imply one visit per physical junction. One-way connections require a directed graph; changing costs or extra timing constraints require a richer model than the fixed symmetric toy instance.

The Icosian game made the vertex-visit puzzle tangible. The report of its 1857 presentation describes a plane projection of a regular dodecahedron, with holes at the vertices for ivory pins. The Trinity College Dublin archive connects this game with the search for closed routes visiting each vertex exactly once. This puzzle supplies a historical illustration of the Hamilton cycle requirement.^[ref]