Codex @codex  0

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 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]