Proof of the Havel-Hakimi Theorem

The Reduction and the Theorem

The Havel–Hakimi reduction gives a step-by-step test for whether a finite list of nonnegative integers can be the degrees of a simple graph. The reduction itself is straightforward to perform. Its key justification is that, whenever the list is graphical, there is a realization in which a vertex of maximum degree is adjacent to the vertices with the next-largest degrees. Edge switches establish this fact without changing any vertex degree.

The condition \(d_1\le n-1\) is necessary for a simple graph: a vertex has at most \(n-1\) other vertices to be adjacent to. When \(d_1=0\), the sequence is all zeros, and the reduction simply deletes one zero. An empty sequence is taken to be graphic, realized by the graph with no vertices.

The two directions explain the theorem’s usefulness. If the reduced sequence is graphic, a new vertex can be added and joined to the vertices whose degrees were reduced. In the other direction, a realization of the original sequence may initially have the wrong neighbors for a maximum-degree vertex. We first prove that edge switches can correct those neighbors.

Why an Edge Switch Preserves Degrees

Proof. The four vertices are distinct, and the two new edges were absent, so adding them creates neither a loop nor a multiple edge. The switch removes one incident edge from each of \(v,u,w,x\) and adds one incident edge to each of them. Every other vertex has the same incident edges as before. Thus all degrees are unchanged. \(\square\)

Proof of the Havel–Hakimi Theorem

Proof. First suppose \(d_1=0\). Since the sequence is nonincreasing and nonnegative, every entry is zero. The original sequence is realized by an edgeless graph, and its reduction, also an all-zero sequence or the empty sequence, is graphic. This proves the equivalence in this case.

Now suppose \(d_1>0\). To prove the forward direction, assume the sequence is graphic and choose a simple graph \(G\) realizing it. Label a vertex \(v\) of degree \(d_1\). Among the other vertices, choose a set \(S\) of \(d_1\) vertices with the largest degrees; if there is a tie at the boundary, choose among the tied possibilities so that \(|N(v)\cap S|\) is as large as possible. Here \(N(v)\) denotes the vertices adjacent to \(v\).

We claim \(v\) can be made adjacent to every vertex of \(S\) by degree-preserving switches. If not, there are vertices \(u\in N(v)\setminus S\) and \(w\in S\setminus N(v)\). Because \(S\) consists of vertices with the largest degrees, \(\deg(w)\ge\deg(u)\). If the degrees were equal, replacing \(u\) in \(S\) by \(w\) would preserve the choice of largest degrees and increase \(|N(v)\cap S|\), contrary to how \(S\) was chosen. Therefore \(\deg(w)>\deg(u)\).

Since \(v\in N(u)\) but \(v\notin N(w)\), the set \(N(u)\setminus N(w)\) contains \(v\). The strict degree inequality gives \(|N(w)\setminus N(u)|>|N(u)\setminus N(w)|\ge1\). Thus \(N(w)\setminus N(u)\) contains at least two vertices. At most one of them is \(u\), so choose \(x\in N(w)\setminus N(u)\) with \(x\ne u\). Also \(x\ne v\), because \(v\notin N(w)\). The edges \(vu\) and \(wx\) are present, while \(vw\) and \(ux\) are absent. These four vertices are distinct, so the lemma allows the switch \(vu,wx\) to \(vw,ux\). It preserves every degree and increases \(|N(v)\cap S|\) by one. Repeating this finitely many times makes every vertex of \(S\) adjacent to \(v\).

Delete \(v\) from this realization. The degrees of the vertices in \(S\) each decrease by one, and all other degrees remain unchanged. The resulting degree list is exactly the list obtained by subtracting one from \(d_2,\ldots,d_{d_1+1}\) and leaving the other entries unchanged; sorting does not change whether it is graphic. Hence the reduction is graphic.

For the reverse direction, assume the reduction is graphic. Assign its degree entries to \(n-1\) vertices so that each has the value it had in the unsorted reduced list: the entries \(d_2-1,\ldots,d_{d_1+1}-1\), followed by \(d_{d_1+2},\ldots,d_n\). This assignment is possible because sorting preserves the list of values. Take a graph realizing those degrees, add a new vertex \(v\), and join \(v\) to the \(d_1\) vertices assigned the first \(d_1\) reduced values. Those vertices each gain one degree, so their degrees become \(d_2,\ldots,d_{d_1+1}\); the others retain degrees \(d_{d_1+2},\ldots,d_n\). The new vertex has degree \(d_1\). Thus the resulting simple graph realizes the original sequence. Both directions hold, proving the theorem. \(\square\)

Worked Examples in Both Directions

Using the Theorem Carefully

The theorem is an equivalence, not just a construction rule: it says that the original sequence is graphic exactly when its reduction is graphic. It does not by itself say that every particular realization has the maximum-degree vertex joined to the largest-degree vertices. The switch argument proves that at least one suitable realization exists, which is enough to establish the reduction step.

Common mistake: subtracting from every remaining entry. For \((3,3,2,2,2,2)\), the correct reduction subtracts one from exactly the next three entries, giving \((2,1,1,2,2)\), then sorts to \((2,2,2,1,1)\). Subtracting one from all five remaining entries instead gives \((2,1,1,1,1)\), a different list. Only the first three remaining entries represent the neighbors required for a vertex of degree \(3\).

Check the degree bound first. For example, \((3,2,1)\) cannot be the degree sequence of a simple graph on three vertices: the first degree \(3\) exceeds the maximum possible degree \(3-1=2\). The theorem’s reduction step is stated under the bound \(d_1\le n-1\); an invalid degree bound is already enough to rule out graphicality.