Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 3 / 14I / c / Solution

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$.