= Solution
Let $v_1\ldots v_k$ be a longest <path> in the finite simple <graph>. Every neighbor of either endpoint lies on this path, since an outside neighbor would extend it. Define two subsets of $\{1,\ldots,k-1\}$:
$$
I=\{i:v_1v_{i+1}\in E\},\qquad J=\{i:v_iv_k\in E\}.
$$
Their sizes are $d(v_1)$ and $d(v_k)$. The degree hypothesis gives $|I|+|J|\geq n\geq k$, but there are only $k-1$ possible indices. Hence some $i$ belongs to both. The edges at that index close a cycle through every vertex of the path:
$$
v_1,v_2,\ldots,v_i,v_k,v_{k-1},\ldots,v_{i+1},v_1.
$$
The <graph> is connected: any component has at least $n/2+1$ vertices by the minimum degree, so two components would exceed $n$ vertices. If $k<n$, connectedness gives an edge from this cycle to an outside vertex. Starting at that vertex and traversing the cycle without its closing edge gives a path with $k+1$ vertices, a contradiction.
Thus $k=n$ and the cycle is a <Hamilton cycle>, proving \b[<Dirac's theorem>]. The overlap-of-indices argument is why the degree threshold is half the number of vertices.
Back to article page
