A Proof of Dirac's Theorem

The Longest-Path Strategy

Dirac’s theorem gives a sufficient condition for a graph to have a Hamiltonian cycle, meaning a cycle that visits every vertex exactly once before returning to its start. The key idea in its proof is to choose a longest path. Its endpoints cannot have neighbors outside the path, since such a neighbor would extend it. The minimum-degree hypothesis therefore puts many neighbors of both endpoints among the path’s vertices. A counting argument forces those neighbors into a useful arrangement, producing a cycle through the entire path.

Throughout, graphs are finite, simple and undirected. The order of \(G\) is \(n=|V(G)|\), and its minimum degree is \(\delta(G)\). A path is a sequence of distinct vertices in which consecutive vertices are adjacent. A longest path is one with as many vertices as possible; it need not be unique.

Proof. If \(v_1\) had a neighbor \(x\) outside \(V(P)\), then \(x,v_1,v_2,\ldots,v_k\) would be a path with \(k+1\) vertices, contradicting the choice of \(P\). If \(v_k\) had a neighbor \(y\) outside \(V(P)\), then \(v_1,\ldots,v_k,y\) would likewise be a path with \(k+1\) vertices. Thus neither endpoint has a neighbor outside \(V(P)\). \(\square\)

The lemma converts degree information into information about positions on one path. The proof will use the \(k-1\) gaps between consecutive vertices of \(P\). If both endpoints have sufficiently many neighbors on the path, some gap must have the two particular endpoint-neighbor incidences needed to close the path into a cycle.

Dirac’s Theorem

Proof. First, \(G\) is connected. Suppose instead that it has at least two connected components. Each component has at least \(\delta(G)+1\) vertices: any vertex in that component has at least \(\delta(G)\) neighbors, all in the same component. Consequently, two components would together contain at least \(2(\delta(G)+1)\ge n+2\) vertices, which is impossible in a graph of order \(n\). Thus \(G\) is connected.

Choose a longest path \(P=v_1v_2\cdots v_k\). Since \(\delta(G)\ge n/2\ge 3/2\), the integer \(\delta(G)\) is at least \(2\), so \(P\) has at least three vertices. By the lemma, all neighbors of its endpoints lie on \(P\).

Index the \(k-1\) gaps along the path by \(1,2,\ldots,k-1\), where gap \(i\) is between \(v_i\) and \(v_{i+1}\). Define two sets of gap indices:

Every neighbor of \(v_1\) is one of \(v_2,\ldots,v_k\), so each such neighbor corresponds to exactly one index in \(A\). Similarly, every neighbor of \(v_k\) is one of \(v_1,\ldots,v_{k-1}\), corresponding to exactly one index in \(B\). Hence \(|A|=\deg(v_1)\) and \(|B|=\deg(v_k)\), and therefore

There are only \(k-1\) possible gap indices. If \(A\) and \(B\) were disjoint, their total size would be at most \(k-1\). The displayed strict inequality rules this out, so there is an index \(i\in A\cap B\). For this index, \(v_1v_{i+1}\) and \(v_iv_k\) are edges. Following the path from \(v_1\) to \(v_i\), taking the edge \(v_iv_k\), then following the path backwards from \(v_k\) to \(v_{i+1}\), and finally taking the edge \(v_{i+1}v_1\), gives a cycle:

If \(i=k-1\), the reverse segment from \(v_{k-1}\) down to \(v_{i+1}\) is empty; the closing edge is then \(v_kv_1\). In every case, each of \(v_1,\ldots,v_k\) appears exactly once before returning to \(v_1\). Thus the cycle contains all vertices of \(P\).

It remains to show that \(P\) contains every vertex of \(G\). If it did not, connectedness would give an edge \(xy\) with \(x\in V(P)\) and \(y\notin V(P)\). The cycle just constructed visits every vertex of \(P\). Starting at \(y\), taking the edge to \(x\), and then following the cycle from \(x\) in one direction while stopping just before returning to \(x\) produces a path containing \(y\) and all \(k\) vertices of \(P\). This path has \(k+1\) vertices, contradicting the maximal length of \(P\). Therefore \(P\) contains all \(n\) vertices, and the cycle is Hamiltonian. \(\square\)

Worked Examples: Finding the Shared Gap

Why the Counting Step Matters

The decisive inequality is not merely that the endpoint degrees are large. It is that the number of indices contributed by the two endpoints is strictly larger than the number of available gaps. Here the number of gaps is \(k-1\), while the hypotheses give \(|A|+|B|\ge n\ge k\). If the sets had no common index, their combined size could not exceed \(k-1\). A shared index supplies both edges needed to close the path while preserving all its vertices.

Common mistake: using a non-strict counting bound. It is not enough, in general, to know that two subsets of a set of size \(r\) have sizes whose sum is at least \(r\). For example, in the universe \(\{1,2\}\), the disjoint sets \(\{1\}\) and \(\{2\}\) have sizes summing to \(2\). The proof needs a sum strictly greater than the universe size. In Dirac’s argument, the relevant comparison is \(|A|+|B|\ge k>k-1\), not merely \(|A|+|B|\ge k-1\).

A second point is that the cycle initially obtained is only known to contain the longest path. The connectedness argument is what rules out vertices outside it: an outside vertex linked to the cycle would let us break the cycle at that link and form a longer path. Both parts of the proof are needed to conclude that the cycle is spanning.