Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 1 / c / Solution

First the graph is connected: every component has at least $\delta (G)+1>n/2$ vertices, so two components cannot fit. Take a longest path $v_1,\dots ,v_k$. Every neighbour of either endpoint lies on that path. In the index set $\{1,\dots ,k-1\}$ defineTheir sizes sum to $d(v_1)+d(v_k)\ge n>k-1$, so they share an index $i$. The edges at that index give the cyclecontaining every vertex of the path. The minimum-degree assumption and $n\ge 3$ ensure the resulting cycle is nondegenerate. If it omitted any graph vertex, connectedness would supply an edge from outside it to the cycle. Starting with that outside vertex and then following the cycle without closing it gives a path with $k+1$ vertices, contradicting maximality. Thus the cycle is Hamiltonian. This proves Dirac's theorem in the required case.