Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 17J / a / Solution

This is Dirac theorem. Take a longest path $v_1\dots v_k$. All neighbours of its ends lie on it. If no index $i$ has both $v_1{v}_{i+1}$ and $v_k{v}_i$, the two end-neighbour sets have total size at most $k-1$, contradicting $2\delta \ge n\ge k$. Such an index closes a cycle through the path, and maximality plus connectedness makes it Hamiltonian. For even $n$, the disjoint union of two copies of $K_{n/2}$ has minimum degree $n/2-1$ and is not Hamiltonian. For odd $n$, $K_{(n-1)/2,(n+1)/2}$ has minimum degree $(n-1)/2$ and no Hamilton cycle because its bipartition sizes differ.