A Systematic Test for Candidate Degree Sequences
A list of nonnegative integers is not automatically the degree sequence of a simple graph. The Erdos-Gallai criterion turns that question into a finite calculation: after sorting the list, check that its sum is even and evaluate a specified inequality at each index. Careful bookkeeping matters. In particular, the terms after the index \(k\), not the first \(k\) terms, appear in the minimum-sum part of the inequality.
Throughout, graphs are finite and simple: they have no loops or multiple edges. A degree sequence is written in nonincreasing order. A sequence is graphic if some simple graph has exactly those vertex degrees.
The left side at index \(k\) is the sum of the first \(k\) degrees. On the right, \(k(k-1)\) accounts for the largest possible total contribution from edges among those \(k\) vertices: each of the \(k\) vertices can have at most \(k-1\) neighbors among them. Each later degree \(d_i\) contributes at most \(k\) edges to the first \(k\) vertices and at most \(d_i\) edges in total, which explains \(\min(k,d_i)\). The criterion says that all these inequalities, together with even total degree, are enough as well as necessary.
Prepare the Sequence Before Calculating
Given a candidate list, first check that its entries are integers and nonnegative. Sort them into nonincreasing order, since the criterion is stated for a sorted sequence. For a simple graph on \(n\) vertices, every degree is at most \(n-1\); an entry greater than \(n-1\) is therefore an immediate obstruction.
Next add the entries. The sum of degrees in a graph is twice its number of edges: every edge has two endpoints and contributes one to the degree of each endpoint. Thus a graphic sequence must have even sum. This is a quick necessary check, but passing it does not establish that the sequence is graphic. If the sum is odd, there is no need to calculate the Erdos-Gallai inequalities.
When the initial checks pass, make a table. For each \(k\), record the prefix sum \(\sum_{i=1}^k d_i\), the right-hand side, and whether the inequality holds. The term \(\min(k,d_i)\) is calculated separately for every \(i>k\). If every row passes, the criterion guarantees the sequence is graphic; if even one row fails, it is not.
Worked Example: A Sequence That Passes Every Inequality
Consider the candidate list \(2,3,2,3,2\). Sort it to obtain \(d=(3,3,2,2,2)\). Its entries are nonnegative integers, and each is at most \(5-1=4\), as required for degrees in a simple graph on five vertices.
The degree sum is \(3+3+2+2+2=12\), which is even. Now evaluate all five inequalities. The table gives the left side \(L_k=\sum_{i=1}^k d_i\) and the right side \(R_k=k(k-1)+\sum_{i=k+1}^5\min(k,d_i)\).
| \(k\) | \(L_k\) | Calculation of \(R_k\) | \(R_k\) | Result |
|---|---|---|---|---|
| 1 | \(3\) | \(0+1+1+1+1\) | \(4\) | \(3\le4\) |
| 2 | \(3+3=6\) | \(2+2+2+2\) | \(8\) | \(6\le8\) |
| 3 | \(3+3+2=8\) | \(6+2+2\) | \(10\) | \(8\le10\) |
| 4 | \(3+3+2+2=10\) | \(12+2\) | \(14\) | \(10\le14\) |
| 5 | \(3+3+2+2+2=12\) | \(20\) | \(20\) | \(12\le20\) |
For example, at \(k=3\), the two entries after \(k\) are both \(2\), so the right side is \(3(3-1)+\min(3,2)+\min(3,2)=6+2+2=10\). Every row passes, and the sum is even. The criterion therefore says that the sequence is graphic.
We can check the conclusion directly. Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51,13\}\). The degrees are \(\deg(1)=3\), \(\deg(2)=2\), \(\deg(3)=3\), \(\deg(4)=2\), and \(\deg(5)=2\). In sorted order these are \(3,3,2,2,2\), as required. The graph has six edges, and the degree sum is \(12=2\cdot6\), providing an additional check.
One Failed Index Is Enough
To rule out a candidate, it is enough to find a single \(k\) for which the left side exceeds the right side. The other inequalities need not be satisfied or even calculated once a failure has been found. Computing the entire table can still be useful when the aim is to document exactly which tests pass and fail.
Worked Example: Finding a Failing Inequality
Test \(d=(4,4,1,1,1,1)\). The entries are sorted nonnegative integers, and each is at most \(6-1=5\). Their sum is \(4+4+1+1+1+1=12\), which is even, so neither of these preliminary checks rules the sequence out.
For each \(k\), calculate the prefix sum and the right side of the criterion:
| \(k\) | \(L_k\) | Calculation of \(R_k\) | \(R_k\) | Result |
|---|---|---|---|---|
| 1 | \(4\) | \(0+1+1+1+1+1\) | \(5\) | \(4\le5\) |
| 2 | \(4+4=8\) | \(2+1+1+1+1\) | \(6\) | \(8>6\) |
| 3 | \(4+4+1=9\) | \(6+1+1+1\) | \(9\) | \(9\le9\) |
| 4 | \(4+4+1+1=10\) | \(12+1+1\) | \(14\) | \(10\le14\) |
| 5 | \(4+4+1+1+1=11\) | \(20+1\) | \(21\) | \(11\le21\) |
| 6 | \(4+4+1+1+1+1=12\) | \(30\) | \(12\le30\) |
The inequality fails at \(k=2\): its left side is \(4+4=8\), while its right side is \(2(2-1)+4\min(2,1)=2+4=6\). Since the sequence violates a required inequality, the Erdos-Gallai criterion says it is not graphic.
Check: the relevant right-side sum uses the four entries after \(d_2\), each of which contributes \(\min(2,1)=1\). Thus it is \(2+1+1+1+1=6\), not \(2+2+2+2+2=10\). The latter incorrectly treats every later degree as at least \(2\).
Why the Procedure Gives the Right Answer
Proof. Let \(d_1\ge\cdots\ge d_n\) be the input list. If its sum is odd, the handshake lemma rules out a graph realization, because every graph has degree sum twice its number of edges. If its sum is even but an inequality fails, the necessary direction of the Erdos-Gallai criterion rules out a realization. Therefore every rejection is correct.
Now suppose the procedure accepts. Its parity check guarantees that the sum is even, and its calculation at every index guarantees all the required inequalities. The sufficient direction of the Erdos-Gallai criterion then guarantees that the list is graphic. Thus acceptance is also correct. For \(n=0\), the separate convention is that the empty sequence is realized by the empty graph, so the procedure accepts it without any checks. \(\square\)
This proposition is a justification of the calculation procedure, not a replacement proof of the Erdos-Gallai theorem. The theorem supplies the mathematical link between the finite checks and the existence of a graph; the procedure ensures that each required check is actually performed.
Parity Can Stop the Test Early
Worked Example: An Odd Degree Sum
Consider \(d=(3,2,2,1,1)\). This is already sorted, and every entry is a nonnegative integer no greater than \(5-1=4\). Its sum is \(3+2+2+1+1=9\), which is odd.
Every graph has an even degree sum: if it has \(m\) edges, each edge contributes \(1\) to the degree of each endpoint, so the total is \(2m\). No integer \(m\) satisfies \(2m=9\). Therefore this list is not graphic, and there is no need to evaluate any of its Erdos-Gallai inequalities.
Check: this rejection uses parity, not a failed inequality. An even sum would only allow the test to continue; it would not by itself prove that the list is graphic, as the preceding example demonstrates.
Common Pitfalls and a Reliable Checklist
A frequent error is to use the wrong entries in the right-hand sum. At a given \(k\), calculate \(k(k-1)\) and then add \(\min(k,d_i)\) for indices \(i=k+1,\ldots,n\). Do not include the first \(k\) entries in that sum. In particular, when \(k=n\), there are no later entries, so the sum of minima is \(0\), and the right side is \(n(n-1)\).
Another error is to treat even degree sum as a complete test. It is necessary but not sufficient: the six-entry example passed the parity check and failed at \(k=2\). Conversely, if an inequality fails, the candidate is nongraphic regardless of how many other inequalities pass.
For a final audit, use the following order:
- Confirm that the input consists of nonnegative integers.
- Sort the entries in nonincreasing order and identify \(n\).
- Check that no entry exceeds \(n-1\), and compute the total sum.
- If the sum is odd, reject immediately; if it is even, calculate the inequalities.
- For each \(k=1,\ldots,n\), write the prefix sum and calculate every later \(\min(k,d_i)\).
- Accept only if every inequality passes. If accepting, an explicit graph realization can provide a direct check of the result.
Check Your Understanding
For each candidate, organize the calculations by index. When a sequence fails, identify a specific reason.
- Test \((3,2,2,1)\). Is the sum even, and what are the left and right sides at every index?
- For \((4,3,2,1,1,1)\), check the entry bounds and sum first. If the parity check passes, evaluate the inequalities until you can decide whether it is graphic.
- Explain why an odd degree sum rules out a graph realization, but an even degree sum does not establish one.
- At \(k=n\), how many terms occur in \(\sum_{i=k+1}^n\min(k,d_i)\)? What is the resulting right side?
- For a sorted sequence \(d_1,\ldots,d_n\), write the Erdos-Gallai inequality at \(k=2\), including exactly which indices appear in the right-hand sum.