The Reduction Idea
A degree sequence records the degrees of the vertices of a graph, arranged in nonincreasing order. The Havel–Hakimi procedure tests such a sequence by repeatedly removing its largest term and reducing other terms. The arithmetic is simple, but the order of operations matters: subtract from the next largest terms, then sort the residual sequence again before continuing.
All graphs considered here are finite and simple. A sequence is graphical if it is the degree sequence of some simple graph. Thus its entries must be nonnegative integers. If the sequence has \(n\) terms, each term must also be at most \(n-1\), because a vertex in a simple graph can be adjacent to at most the other \(n-1\) vertices.
If \(d_1=0\), the sequence is already all zeros, since it is nonincreasing and all entries are nonnegative. This is a successful stopping point. Otherwise, after a valid reduction, repeat the procedure on the shorter sorted sequence. A negative term means failure; do not continue by treating it as an ordinary degree.
The procedure also requires an initially valid input form: a finite nonincreasing sequence of nonnegative integers. If a sequence is supplied unsorted, first sort it. If it contains a negative or noninteger entry, it cannot be a degree sequence. Sorting is not optional after a reduction: the next step must remove a largest remaining term.
What Each Step Guarantees
Proof. Write the sequence as \(d_1\ge d_2\ge\cdots\ge d_n\), with \(d_1=r\). Removing \(d_1\) removes \(r\) from the sum. Subtracting \(1\) from exactly \(r\) other terms reduces the sum by another \(r\). Reordering does not change the sum. Thus the new sum is the old sum minus \(2r\), which is even, so the old and new sums have the same parity. Exactly one term was removed, and later reductions also remove one term each; therefore there can be at most \(n\) reductions before there are no terms left. In practice, the all-zero sequence can be declared successful as soon as it appears. \(\square\)
This bookkeeping is useful, but it is not by itself a graphicality test: preserving an even sum does not ensure that the sequence is graphical. The algorithm’s full criterion is the Havel–Hakimi theorem: a nonincreasing sequence of nonnegative integers is graphical if and only if its Havel–Hakimi reduction is graphical, with the all-zero sequence as the stopping case. The theorem’s proof is given in the next part of the course. Here we use the procedure to carry out the reductions and interpret their outcomes.
Sort the nonnegative integer terms in nonincreasing order. Check that the largest term is no more than one less than the number of terms.
If it is \(r\), delete it and subtract \(1\) from the next \(r\) terms.
If a term became negative, report failure. Otherwise, sort the residual terms in nonincreasing order.
If all residual terms are zero, the procedure succeeds. If not, apply the same steps to the residual sequence.
Worked Reductions
Worked Example: Reduction to Zero
Apply the procedure to \((3,3,2,2,2)\).
The sequence is already nonincreasing. Its largest term is \(3\), and there are \(5\) terms, so \(3\le 5-1=4\). Remove the first \(3\), then subtract \(1\) from the next \(3\) terms: \(3-1=2\), \(2-1=1\), and \(2-1=1\). The untouched final term is \(2\). The residual list is therefore \((2,1,1,2)\), which sorts to \((2,2,1,1)\).
Now remove \(2\). Subtract \(1\) from the next two terms: \(2-1=1\) and \(1-1=0\); the last term remains \(1\). This gives \((1,0,1)\), which sorts to \((1,1,0)\).
Remove \(1\), subtract \(1\) from the next term, and leave the last term unchanged: \(1-1=0\), with the other term \(0\). The result is \((0,0)\), so the procedure succeeds.
Check: The successive sums are \(3+3+2+2+2=12\), \(2+2+1+1=6\), \(1+1+0=2\), and \(0+0=0\). The reductions remove largest terms \(3,2,1\), so the sum drops by \(2\cdot3=6\), then \(2\cdot2=4\), then \(2\cdot1=2\), as required by the proposition. As an independent check of graphicality, take \(V=\{A,B,C,D,E\}\) and \(E=\{AB,AC,AD,BC,BE,DE\}\). The degrees are \(3,3,2,2,2\): \(A\) and \(B\) each have three incident edges, and \(C,D,E\) each have two.
Worked Example: Failure After a Valid First Step
Apply the procedure to \((3,3,1,1,0)\). This is a nonincreasing sequence of nonnegative integers, and its largest term satisfies \(3\le 5-1=4\).
Remove the first \(3\) and subtract \(1\) from the next three terms. The subtractions are \(3-1=2\), \(1-1=0\), and \(1-1=0\). The final term remains \(0\), so the residual sequence is \((2,0,0,0)\), already sorted.
At the next step, the largest term is \(2\), but only three terms remain, so \(2\le3-1=2\) and the size bound is satisfied. Remove the \(2\) and subtract \(1\) from each of the next two terms: \(0-1=-1\) and \(0-1=-1\). The negative results mean that this reduction fails; the sequence cannot continue to the all-zero stopping case.
Check: The initial sum is \(3+3+1+1+0=8\), and the first residual sum is \(2+0+0+0=2\), a decrease of \(6=2\cdot3\). The next arithmetic gives \(-1\) and \(-1\), not valid degrees. The initial sum is even, so parity alone would not have detected this failure.
Worked Example: A Zero Term and an All-Zero Input
Start with \((2,1,1,0)\). Remove the largest term \(2\) and subtract \(1\) from the next two terms: \(1-1=0\) and \(1-1=0\). The last term remains \(0\), so the residual sequence is \((0,0,0)\), which is already sorted and all zero. The procedure succeeds without needing another subtraction.
For an input that begins with zeros, consider \((0,0,0)\). Its largest term is \(0\). No terms are subtracted from, and the sequence is already all zero, so the procedure succeeds immediately.
Check: In the first sequence, the sum is \(2+1+1+0=4\); after removing \(2\) and subtracting twice, it is \(0+0+0=0\), a decrease of \(4=2\cdot2\). In the second sequence the sum is \(0+0+0=0\), and no reduction is needed. Both inputs meet the nonnegative-integer and nonincreasing conditions.
Reading the Output Carefully
A successful run ends with an all-zero sequence. Under the Havel–Hakimi theorem, this means the original sequence is graphical. A failed run may stop because the largest term is too large for the number of remaining terms, or because subtracting from the requested terms creates a negative entry. Under the same theorem, such a failure means the original sequence is not graphical. In both cases, the result concerns the original sequence, not just the final list considered in isolation.
There is a simple reason the size check must be repeated at each stage. After a reduction, the number of terms is smaller. A term that was at most \(n-1\) initially might exceed the maximum allowed degree in the residual sequence. For example, with residual sequence \((3,1,1)\), there are three terms, and \(3>3-1=2\); the largest term cannot be reduced according to the procedure.
The sum check can identify some failures quickly. By the handshake lemma, a graph’s degree sum is twice its number of edges, so a graphical sequence must have even sum. The proposition shows that valid Havel–Hakimi reductions preserve the sum’s parity. However, an even sum is only a necessary condition, not a sufficient one: the example \((3,3,1,1,0)\) has even sum \(8\), yet its reductions produce negative entries.
Common Pitfalls
Subtracting from the wrong terms. For \((3,3,2,2,2)\), removing \(3\) means subtracting \(1\) from the next three terms, not from all four remaining terms. The correct list before sorting is \((2,1,1,2)\), which sorts to \((2,2,1,1)\). Subtracting from all four would produce \((2,1,1,1)\), an incorrect reduction.
Forgetting to reorder. After that correct first step, the list \((2,1,1,2)\) is not in nonincreasing order. Removing its first displayed term without sorting is not a valid next step. Sort it to \((2,2,1,1)\), then remove a largest term.
Continuing after a negative term appears. A negative entry is not a degree and is the stopping signal for failure, not a value to carry into another subtraction. Also, a zero largest term means every term is zero only when the sequence is already sorted and nonnegative; these input conditions are part of the procedure.
Check Your Understanding
For each question, show the subtractions and any reordering explicitly.
- Reduce \((2,2,1,1)\) until it succeeds or fails. At each step, state the sum before and after the reduction.
- What is the first failure in applying the procedure to \((4,2,2,0,0)\)?
- Explain why subtracting from more than the largest term’s number of following entries is not the Havel–Hakimi reduction.
- Prove that a valid reduction preserves the parity of the degree sum.
- Why does an even initial sum not guarantee that the procedure succeeds?