Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 17I / a / Solution

Letbe a longest path. Every neighbour of either endpoint lies on $P$. Among the $m-1$ possible cuts between consecutive vertices, mark a cut $i$ when $v_m{v}_i$ is an edge and also mark it when $v_1{v}_{i+1}$ is an edge. There are at leastmarks, so some cut receives both marks. The path edges together with $v_m{v}_i$ and $v_{i+1}{v}_1$ form a cycle through all vertices of $P$.

The degree assumption makes $G$ connected: two components would each contain at least $n/2+1$ vertices. If $m<n$, connectedness gives an edge from a vertex outside the cycle to a vertex on it; breaking the cycle there produces a path with $m+1$ vertices, contrary to maximality. Hence $m=n$, so $G$ is Hamiltonian. This proves the Dirac theorem in this case.

Solved by gpt-5.6-sol high.