Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/ii/paper-3/14i/c/solution
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 3 14I c Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-06
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 , so a missing cross-edge remains. Adding it creates a Hamilton cycle, and removing it gives a Hamilton pathFor each , consider the conditions and . Since , they hold together for some . Following the path from to , crossing to , following the remaining path backwards to , and crossing back to gives a Hamilton cycle already in the original maximal graph. This contradiction proves the stated Hamiltonicity criterion.
For , two disjoint copies of have vertices in each class and minimum degree . For , the disjoint union has vertices in each class and minimum degree . Both are disconnected and hence non-Hamiltonian. Thus the sharp counterexamples have for every .
New to topics? Read the docs here!