From Degree Bounds to a Complete Test
A nonincreasing list of nonnegative integers is graphic if it is the degree sequence of a finite simple graph. The handshake lemma gives an immediate necessary condition: the sum of the degrees must be even. The degree bound for simple graphs also requires each entry to be at most \(n-1\), where \(n\) is the number of entries. These checks are useful, but neither alone is a complete test. The Erdős–Gallai criterion supplies a family of inequalities that, together with even sum, gives an exact characterization.
Throughout, a graph is finite and simple: it has no loops or multiple edges. Write the proposed degree sequence in nonincreasing order as \(d_1\ge d_2\ge\cdots\ge d_n\ge0\). For a positive integer \(k\le n\), the first \(k\) entries are the \(k\) largest proposed degrees.
The right side has a direct interpretation. Among \(k\) selected vertices, at most \(k(k-1)\) degree incidences can come from edges with both ends among those vertices: there are at most \(\binom{k}{2}\) such edges, each contributing two incidences. Each vertex outside the selected group can contribute at most \(k\) edges to it, and at most its own degree \(d_i\). This explains the term \(\min(k,d_i)\).
Why the Inequalities Are Necessary
We first prove the direction that follows by counting. This also explains why the test uses the largest \(k\) degrees.
Proof. Suppose \(G\) is a simple graph with degree sequence \(d_1\ge\cdots\ge d_n\), and fix \(k\) with \(1\le k\le n\). Let \(S\) be a set of \(k\) vertices whose degrees are \(d_1,\ldots,d_k\). The sum \(\sum_{i=1}^k d_i\) counts incidences at vertices in \(S\). Edges with both ends in \(S\) contribute two each, and there are at most \(\binom{k}{2}\) such edges, so these incidences total at most \(2\binom{k}{2}=k(k-1)\). For each vertex outside \(S\), at most \(k\) of its incident edges can end in \(S\), and it has only \(d_i\) incident edges in total. Its contribution is therefore at most \(\min(k,d_i)\). Summing over vertices outside \(S\) proves the stated inequality. The handshake lemma gives \(\sum_{i=1}^n d_i=2|E(G)|\), which is even. \(\square\)
The inequality at \(k=n\) also bounds the total degree sum by \(n(n-1)\), the total possible degree sum in a simple graph. But the intermediate inequalities can rule out a sequence even when the total sum is even and small enough.
Worked Examples
Worked Example: Verifying a Graphic Sequence
Test the sequence \((3,3,2,2,2)\). It is nonincreasing, has \(n=5\), and has even sum \(3+3+2+2+2=12\). The Erdős–Gallai theorem says it is graphic if all five inequalities hold.
For \(k=1\), the left side is \(3\), and the right side is \(0+\min(1,3)+\min(1,2)+\min(1,2)+\min(1,2)=4\). Thus \(3\le4\).
For \(k=2\), the left side is \(3+3=6\), and the right side is \(2+ \min(2,2)+\min(2,2)+\min(2,2)=8\). Thus \(6\le8\).
For \(k=3\), the left side is \(3+3+2=8\), and the right side is \(3\cdot2+\min(3,2)+\min(3,2)=10\). Thus \(8\le10\).
For \(k=4\), the left side is \(3+3+2+2=10\), and the right side is \(4\cdot3+\min(4,2)=14\). Thus \(10\le14\).
For \(k=5\), the left side is \(12\), and the right side is \(5\cdot4=20\). All the conditions hold, so the sequence is graphic.
Check: The graph with \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,23,25,45\}\) has degrees \(3,3,2,2,2\): vertices \(1,2,3,4,5\) have degrees \(3,3,2,2,2\), respectively. It realizes the sequence. Its six edges give total degree \(2\cdot6=12\), agreeing with the sum above.
Worked Example: Even Sum Is Not Enough
Test \((3,3,1,1,0)\). The entries are nonincreasing, and their sum is \(3+3+1+1+0=8\), which is even. For \(k=1\), the left side is \(3\), while the right side is \(\min(1,3)+\min(1,1)+\min(1,1)+\min(1,0)=3\), so that inequality holds.
For \(k=2\), the left side is \(3+3=6\). The right side is \(2\cdot1+\min(2,1)+\min(2,1)+\min(2,0)=4\). Since \(6>4\), the criterion fails, and the sequence is not graphic.
Check: If two vertices both had degree \(3\), their combined degree sum would be \(6\). They can have at most one edge between them, accounting for at most \(2\) of those incidences. The other three vertices have proposed degrees \(1,1,0\), so they can supply at most \(1+1+0=2\) incidences to the two high-degree vertices. The total available is at most \(2+2=4\), less than \(6\). This is exactly the failed \(k=2\) inequality.
Worked Example: Zero Entries and the End Inequalities
Test \((2,2,2,0,0)\). Its sum is \(2+2+2+0+0=6\), which is even. For \(k=1\), the left side is \(2\), and the right side is \(\min(1,2)+\min(1,2)+\min(1,0)+\min(1,0)=2\).
For \(k=2\), the left side is \(2+2=4\); the right side is \(2+\min(2,2)+\min(2,0)+\min(2,0)=4\). For \(k=3\), the left side is \(6\), and the right side is \(3\cdot2+\min(3,0)+\min(3,0)=6\). For \(k=4\), the left side is \(6\), and the right side is \(4\cdot3+\min(4,0)=12\). For \(k=5\), the left side is \(6\), and the right side is \(5\cdot4=20\). Thus every inequality holds, including those in which some outside degrees are zero. The sequence is graphic.
Check: Take \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,23\}\). The first three vertices each have degree \(2\), and the last two have degree \(0\), so the graph realizes the sequence. There are three edges, and the degree sum is \(2\cdot3=6\).
The Sufficiency Direction
The converse says that every sequence passing the tests is graphic. This is the harder half of the theorem, and it is due to Erdős and Gallai (1960). Short proofs proceed by induction and check that the inequalities survive each reduction step, for example Choudum (1986) and Tripathi and Vijay (2003). The case analysis in those proofs is longer than this tutorial can carry, so we prove necessity in full above and cite sufficiency as a theorem.
What we can do explicitly is build a graph once the tests pass. The Havel–Hakimi reduction does this. It is the standard constructive companion to the criterion.
Reading the theorem from right to left gives a construction: realize the smaller sequence, add a new vertex, and join it to the \(r\) vertices whose degrees were lowered.
Worked Example: Building a Graph for \((3,3,2,2,2)\)
Call the vertices \(a,b,c,d,e\), with degrees \(3,3,2,2,2\). Remove \(a\) and subtract \(1\) from the next three entries, \(b,c,d\). The remaining degrees are \(b:2,\ c:1,\ d:1,\ e:2\), which sort to \((2,2,1,1)\) on the vertices \(b,e,c,d\).
Remove \(b\) and subtract \(1\) from the next two entries, \(e\) and \(c\). The remaining degrees are \(e:1,\ c:0,\ d:1\), which sort to \((1,1,0)\) on \(e,d,c\). Remove \(e\) and subtract \(1\) from \(d\). The result is \((0,0)\) on \(d,c\), which is realized by the graph with no edges.
Now reverse each step. Add \(e\) joined to \(d\); add \(b\) joined to \(e\) and \(c\); add \(a\) joined to \(b,c,d\). The edge set is \(E=\{ed,\ be,\ bc,\ ab,\ ac,\ ad\}\).
Check: \(\deg a=3\) (\(b,c,d\)), \(\deg b=3\) (\(a,c,e\)), \(\deg c=2\) (\(a,b\)), \(\deg d=2\) (\(a,e\)), and \(\deg e=2\) (\(b,d\)). The six edges give degree sum \(12\), as required.
Using the Criterion Carefully
The theorem is an exact test only when all its hypotheses are observed: the entries must be integers, nonnegative, and sorted in nonincreasing order; the sum must be even; and every inequality from \(k=1\) through \(k=n\) must hold. The entries need not be distinct. Zero degrees are allowed and represent isolated vertices.
A common mistake is to check only the parity condition and the \(k=n\) inequality. For \((3,3,1,1,0)\), the sum is even and \(8\le5\cdot4=20\), but the \(k=2\) inequality fails because \(6>4\). Another mistake is to omit the cap \(\min(k,d_i)\): outside vertices cannot contribute more than \(k\) edges to a set of \(k\) vertices, even if their degrees exceed \(k\).
Finally, necessity and sufficiency play different roles. The incidence count proves that every graph must pass the inequalities. The converse, that passing all the inequalities guarantees a graph exists, is the cited sufficiency theorem, and the Havel–Hakimi construction produces such a graph whenever the tests pass.
Check Your Understanding
For each sequence, first check the ordering and sum, then test the relevant Erdős–Gallai inequalities.
- For \((2,2,1,1)\), compute the inequalities for \(k=1,2,3,4\). Is the sequence graphic?
- For \((4,1,1,1,1)\), identify a failed Erdős–Gallai inequality and explain its counting meaning.
- Why does the \(k=1\) inequality imply \(d_1\le n-1\)?
- Explain why an outside vertex of degree \(d_i\) contributes at most \(\min(k,d_i)\) to the degree sum of a chosen \(k\)-vertex set.
- What does a zero entry mean in a realization, and why does it cause no special exception in the criterion?