= 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\geq2$, so a missing cross-edge $uv$ remains. Adding it creates a Hamilton cycle, and removing it gives a Hamilton path
$$
u=A_1,B_1,A_2,B_2,\ldots,A_n,B_n=v.
$$
For each $i$, consider the conditions $uB_i\in E$ and $A_iv\in E$. Since $\deg u+\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 \b[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}\sqcup K_{m+1,m}$ has $n$ vertices in each class and minimum degree $m$. Both are disconnected and hence non-Hamiltonian. Thus \b[the sharp counterexamples have] $\boxed{\delta=\lfloor n/2\rfloor}$ for every $n\geq2$.
Back to article page
