Two Tests for One Question
A list of nonnegative integers is graphical if it is the degree sequence of a finite simple graph. Havel–Hakimi and Erdős–Gallai test this same property, but organize the work differently. Havel–Hakimi repeatedly transforms the sequence into a shorter one. Erdős–Gallai keeps the sequence fixed and checks a family of inequalities. Comparing them is useful because each test gives a different kind of evidence: a reduction trace or an inequality certificate.
Throughout, sequences are written in nonincreasing order, so \(d_1\ge d_2\ge\cdots\ge d_n\ge0\), and their entries are integers. A candidate for a simple graph on \(n\) vertices must also have \(d_i\le n-1\) for every \(i\), and its degree sum must be even. These preliminary checks are necessary, but by themselves they do not establish graphicality.
The Havel–Hakimi theorem says that, when \(d\le n-1\), \(D\) is graphical if and only if its Havel–Hakimi reduction is graphical. This theorem was proved in the earlier material on Havel–Hakimi. Repeating the reduction gives a test: reaching an all-zero sequence means success; encountering a negative entry means failure. The sequence gets shorter at every reduction, so the process terminates.
\(\displaystyle \sum_{i=1}^{k}d_i\le k(k-1)+\sum_{i=k+1}^{n}\min(k,d_i).\)
For a sequence of nonnegative integers to be graphical, its sum must be even and all these inequalities must hold.
The Erdős–Gallai criterion, proved in the earlier material on that criterion, states that a sorted sequence of nonnegative integers is graphical if and only if its sum is even and it satisfies every displayed inequality. Thus the criterion is not a selection of a few convenient inequalities: it requires checking all \(k=1,\ldots,n\). The empty final sum on the right when \(k=n\) is \(0\).
What the Tests Have in Common—and What They Do Differently
| Feature | Havel–Hakimi | Erdős–Gallai |
|---|---|---|
| Operation | Remove the largest entry, reduce the next entries, and sort again. | Keep the original sorted sequence and evaluate inequalities. |
| Typical success evidence | A sequence of reductions ending in zeros. | Even total degree and every inequality satisfied. |
| Typical failure evidence | A reduction demands more entries than remain or produces a negative entry. | A specific inequality has its left side larger than its right side. |
| What acceptance establishes | Graphicality, by the Havel–Hakimi theorem. | Graphicality, by the Erdős–Gallai criterion. |
The tests are equivalent as decision procedures: under the stated assumptions, either both accept a graphical sequence or both reject a nongraphical one. Their intermediate calculations need not look alike. One follows successive smaller sequences; the other compares degree sums across initial segments with a bound involving the remaining entries.
Proof. The Havel–Hakimi theorem states that the reduction process accepts \(D\) if and only if \(D\) is graphical. The Erdős–Gallai criterion states that, for a nonnegative integer sequence with even sum, \(D\) is graphical if and only if all its inequalities hold. Therefore Havel–Hakimi accepts \(D\) if and only if \(D\) is graphical, which holds if and only if all the Erdős–Gallai inequalities hold. \(\square\)
This comparison invokes the two named criteria proved in the earlier course material; it does not replace either criterion’s proof. It does show why the tests’ verdicts must agree when their hypotheses are met. A failed reduction and a failed inequality are different ways to detect nongraphicality, not conflicting verdicts.
Proof. Removing the first entry subtracts \(d\) from the sequence total. The \(d\) subtractions from the next entries remove another \(d\) in total. Sorting does not change the sum, so the total decreases by \(d+d=2d\). In particular, an even total remains even after every valid reduction. \(\square\)
Worked Comparisons
Worked Example: Both Tests Accept
Consider \(D=(3,3,2,2,2)\). Its entries are nonnegative and at most \(5-1=4\), and its sum is \(3+3+2+2+2=12\), which is even. Apply both tests.
Havel–Hakimi. Remove the first \(3\) and subtract \(1\) from the next three entries \(3,2,2\). The entries left are \(2,1,1,2\), which sort to \((2,2,1,1)\). Remove the first \(2\) and subtract \(1\) from the next two entries \(2,1\); the remaining entries are \(1,0,1\), which sort to \((1,1,0)\). Remove the first \(1\) and subtract \(1\) from the next entry \(1\), leaving \((0,0)\). The next reduction removes a zero and leaves \((0)\); removing that zero leaves the empty sequence. No negative entry occurs, so the test accepts.
Erdős–Gallai. Check each \(k\), with the left and right sides shown separately:
- \(k=1\): \(3\le 0+\min(1,3)+\min(1,2)+\min(1,2)+\min(1,2)=4\).
- \(k=2\): \(3+3=6\le 2+\min(2,2)+\min(2,2)+\min(2,2)=8\).
- \(k=3\): \(3+3+2=8\le 3\cdot2+\min(3,2)+\min(3,2)=10\).
- \(k=4\): \(3+3+2+2=10\le 4\cdot3+\min(4,2)=14\).
- \(k=5\): \(3+3+2+2+2=12\le 5\cdot4=20\).
Every inequality holds, and the degree sum is even, so the criterion accepts. As an independent check, take \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,23,25,45\}\). The degrees are \(3,3,2,2,2\): vertex \(1\) is incident with \(12,13,14\); vertex \(2\) with \(12,23,25\); and vertices \(3,4,5\) each have degree \(2\). This explicitly realizes the sequence.
Worked Example: Both Tests Reject
Consider \(D=(4,4,1,1,1,1)\). The entries are nonnegative and at most \(6-1=5\), and the sum is \(4+4+1+1+1+1=12\), which is even. Thus neither the degree bound nor parity alone detects a problem.
Erdős–Gallai. At \(k=1\), the left side is \(4\), while the right side is \(0+\min(1,4)+\min(1,1)+\min(1,1)+\min(1,1)+\min(1,1)=5\), so this inequality holds. At \(k=2\), the left side is \(4+4=8\), while the right side is \(2+\min(2,1)+\min(2,1)+\min(2,1)+\min(2,1)=6\). Since \(8>6\), this single failed inequality proves that \(D\) is not graphical; there is no need to check further \(k\).
Havel–Hakimi. Remove the first \(4\) and subtract \(1\) from the next four entries \(4,1,1,1\). The entries left are \(3,0,0,0,1\), which sort to \((3,1,0,0,0)\). Now remove \(3\) and subtract \(1\) from the next three entries \(1,0,0\). This produces \(0,-1,-1\), as well as the remaining \(0\). The negative entries show that the reduction fails. Both tests therefore reject, for different visible reasons.
Worked Example: A Short Reduction and the Inequality Checks
Take \(D=(2,2,2,2,0)\). Its sum is \(2+2+2+2+0=8\), which is even, and each entry is at most \(5-1=4\).
Havel–Hakimi. Remove the first \(2\) and subtract \(1\) from the next two entries, both equal to \(2\). The remaining entries are \(1,1,2,0\), which sort to \((2,1,1,0)\). Remove the first \(2\) and subtract \(1\) from the next two entries \(1,1\). This leaves \((0,0,0)\). Removing zeros leaves only zeros, so the test accepts.
Erdős–Gallai. At \(k=1\), the left side is \(2\), and the right side is \(0+\min(1,2)+\min(1,2)+\min(1,2)+\min(1,0)=3\), so \(2\le3\). At \(k=2\), the left side is \(2+2=4\), and the right side is \(2+\min(2,2)+\min(2,2)+\min(2,0)=6\), so \(4\le6\). At \(k=3\), the left side is \(2+2+2=6\), and the right side is \(3\cdot2+\min(3,2)+\min(3,0)=8\), so \(6\le8\). At \(k=4\), the left side is \(8\), and the right side is \(4\cdot3+\min(4,0)=12\), so \(8\le12\). At \(k=5\), the left side is \(8\), and the right side is \(5\cdot4=20\), so \(8\le20\). All five inequalities hold.
For a direct realization, let \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,41\}\). Vertices \(1,2,3,4\) each have degree \(2\), and vertex \(5\) has degree \(0\). The degree sequence is exactly \((2,2,2,2,0)\).
How to Choose and Check a Test
For a hand calculation, Havel–Hakimi is often convenient when a few reductions quickly reach zeros or produce a negative entry. Erdős–Gallai is useful when one initial-segment inequality fails early, as in the second example. If all inequalities hold, however, the full list \(k=1,\ldots,n\) must be checked; passing only \(k=1\) and \(k=2\) is not enough.
The reduction lemma gives a useful arithmetic check on a Havel–Hakimi trace: each valid step lowers the sum by an even number. If a calculation changes the total by anything other than twice the removed entry, an entry was likely omitted or decremented incorrectly. For Erdős–Gallai, check the indices carefully: when testing \(k\), the left side uses exactly the first \(k\) entries, and the right-hand sum uses every entry after \(d_k\), each capped by \(k\).
Common mistake: omitting a tail entry. For \(D=(2,2,2,2,0)\) at \(k=2\), the tail consists of three entries, \(2,2,0\). A wrong calculation might write the right side as \(2+\min(2,2)+\min(2,0)=4\), omitting one of the tail entries equal to \(2\). The correct calculation includes all entries after the first two: \(2+\min(2,2)+\min(2,2)+\min(2,0)=6\). The inequality is \(4\le6\), not \(4\le4\). Always count the tail terms: there are \(n-k\) of them.
Both methods require careful sorting. After a Havel–Hakimi reduction, sort again before choosing the next largest entry. In an Erdős–Gallai check, use a nonincreasing sequence so that “the first \(k\)” has the required meaning. Finally, acceptance has a precise interpretation: under the hypotheses of the relevant criterion, the sequence is realizable by a simple graph. A reduction trace or a list of inequalities is not itself a drawing, but each is a valid certificate of the test’s conclusion.
Check Your Understanding
For each question, show the arithmetic that supports your conclusion.
- For \(D=(3,2,2,1,1)\), compute the first Havel–Hakimi reduction and state the resulting sorted sequence.
- For \(D=(3,2,2,1,1)\), check the Erdős–Gallai inequality at \(k=1\). Does passing this one inequality establish graphicality?
- Explain why the sequence \((4,4,1,1,1,1)\) passes the even-sum check but is still nongraphical.
- In a valid Havel–Hakimi step that removes \(d=3\), by how much does the total degree sum decrease? Justify the answer.
- For an Erdős–Gallai check at \(k=2\) on a sequence of length \(7\), how many terms occur in the tail sum, and which entries do they use?