= Solution
Let
$$
P=v_1v_2\cdots v_m
$$
be 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_1v_{i+1}$ is an edge. There are at least
$$
d(v_m)+d(v_1)\geq n>m-1
$$
marks, so some cut receives both marks. The path edges together with $v_mv_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.
Back to article page
