{c}

= Hamiltonian cycle
{c}
{synonym}

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|\geq3$. A traversal is a <sequence>
$$
v_0,v_1,\ldots,v_{n-1},v_n=v_0,
$$
where $v_0,\ldots,v_{n-1}$ are all the distinct <vertices> and $\{v_i,v_{i+1}\}\in E$ for $0\leq 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>.<Graph Theory by Reinhard Diestel/Hamilton Cycles>[Diestel, Graph Theory, Chapter 10, opening paragraph, printed p. 323: Hamilton cycles, Hamilton paths, and the contrast with Euler tours]{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.

\Image[/hamilton-euler-vertex-edge-comparison.png]
{title=Two <graphs> separate <Hamilton cycle> vertex coverage from <Euler circuit> edge coverage; arrows mark traversal order, not directed <edges>}
{id=hamilton-euler-vertex-edge-comparison}

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.


 Hamilton cycle (source code)