Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-1/17i/a/solution
Past exam of the mathematics course of the University of Cambridge 2024 ii Paper 1 17I a Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Letbe a longest path. Every neighbour of either endpoint lies on . Among the possible cuts between consecutive vertices, mark a cut when is an edge and also mark it when is an edge. There are at leastmarks, so some cut receives both marks. The path edges together with and form a cycle through all vertices of .
The degree assumption makes connected: two components would each contain at least vertices. If , connectedness gives an edge from a vertex outside the cycle to a vertex on it; breaking the cycle there produces a path with vertices, contrary to maximality. Hence , so is Hamiltonian. This proves the Dirac theorem in this case.
New to topics? Read the docs here!