= Necessary conditions for a Hamilton cycle
A <Hamiltonian graph> must be a <connected graph> and have <minimum degree> $\delta(G)\geq2$: 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>.<Graph Theory by Reinhard Diestel/Hamilton Cycles>[Diestel, Graph Theory, §10.1, printed pp. 323–324: necessary minimum degree two and 2-connectivity]{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\geq3$ and $\delta(G)\geq 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$.<Graph Theory by Reinhard Diestel/Hamilton Cycles>[Diestel, Graph Theory, §10.1, Theorem 10.1.1, printed p. 324]{ref}
Back to article page
