Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 3 / 14I (Graph Theory)

A Hamilton cycle is a cycle graph which visits every vertex of a finite graph exactly once, apart from returning to its starting vertex. A graph is Hamiltonian when it contains such a cycle.

Let $v_1\cdots v_k$ be a longest path. Every neighbour of either endpoint lies on it. Among the $k-1$ indices $i=1,\dots ,k-1$, mark those with $v_1{v}_{i+1}$ an edge and those with $v_i{v}_k$ an edge. Their total number isso some index has both marks. The edges at that index close the path into the cycle graphThe minimum-degree hypothesis also forces the graph to be a connected graph: each component would otherwise have at least $n/2+1$ vertices. If $k<n$, an edge from this cycle to an outside vertex would give a longer path by opening the cycle at its incident vertex. Hence $k=n$, proving the Dirac theorem and Hamiltonicity.

The bound is sharp. For $n=2m$, take two disjoint copies of $K_m$, with minimum degree $m-1$. For $n=2m+1$, take two copies of $K_{m+1}$ sharing exactly one vertex. The minimum degree is $m$, but the shared vertex is a cut vertex, which no Hamiltonian graph can have. Both constructions have

Add missing cross-edges to a hypothetical non-Hamiltonian balanced bipartite graph until it is maximal with that property. The complete bipartite graph is Hamiltonian for $n\ge 2$, so a missing cross-edge $uv$ remains. Adding it creates a Hamilton cycle, and removing it gives a Hamilton pathFor each $i$, consider the conditions $u{B}_i\in E$ and $A_{i}v\in E$. Since $\mathrm{deg}u+\mathrm{deg}v>n$, they hold together for some $i$. Following the path from $u$ to $A_i$, crossing to $v$, following the remaining path backwards to $B_i$, and crossing back to $u$ gives a Hamilton cycle already in the original maximal graph. This contradiction proves the stated Hamiltonicity criterion.

For $n=2m$, two disjoint copies of $K_{m,m}$ have $n$ vertices in each class and minimum degree $m$. For $n=2m+1$, the disjoint union $K_{m,m+1}\bigsqcup K_{m+1,m}$ has $n$ vertices in each class and minimum degree $m$. Both are disconnected and hence non-Hamiltonian. Thus the sharp counterexamples have $\boxed{\delta =\lfloor n/2\rfloor }$ for every $n\ge 2$.