= Solution
This is <Dirac theorem>. Take a longest path $v_1\ldots v_k$. All neighbours of its ends lie on it. If no index $i$ has both $v_1v_{i+1}$ and $v_kv_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.
Back to article page
