Degree Sequence Realizability

A fundamental question in graph theory asks: given a sequence of non-negative integers, does there exist a graph with those vertex degrees? The Erdős-Gallai theorem provides a complete characterization through a simple computable criterion.

DefinitionDegree Sequence

A degree sequence is a non-increasing sequence $d_1 \geq d_2 \geq \cdots \geq d_n$ of non-negative integers. The sequence is graphical (or realizable) if there exists a simple graph $G$ with vertices $v_1, \ldots, v_n$ such that $\deg(v_i) = d_i$ for all $i$ .

TheoremErdős-Gallai Theorem

A non-increasing sequence $(d_1, d_2, \ldots, d_n)$ of non-negative integers is graphical if and only if:

The sum $\sum_{i=1}^n d_i$ is even
For each $k \in \{1, \ldots, n\}$ : $\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min(d_i, k)$

The first condition follows from the handshaking lemma. The second condition is more subtle: it states that the sum of the first $k$ largest degrees cannot exceed the maximum possible edges within those $k$ vertices plus the edges to the remaining vertices (bounded by what those vertices can support).

ProofProof Sketch

( $\Rightarrow$ ) If $G$ realizes the sequence, condition (1) holds by the handshaking lemma. For (2), consider the $k$ vertices with highest degrees. They can have at most $k(k-1)$ edges among themselves. Each can have at most $\min(d_i, k)$ edges to the remaining $n-k$ vertices: either $d_i$ edges total (if $d_i \leq k$ ) or at most $k$ edges to those vertices.

( $\Leftarrow$ ) The forward direction is algorithmic: use the Havel-Hakimi algorithm. Given $d_1 \geq \cdots \geq d_n$ , connect vertex $v_1$ to $v_2, \ldots, v_{d_1+1}$ , reduce their degrees by 1, remove $v_1$ , and recurse. The Erdős-Gallai conditions ensure this process succeeds.

■

ExampleTesting Graphical Sequences

Consider the sequence $(4, 3, 3, 2, 2)$ . First, $\sum d_i = 14$ is even. Check $k=1$ : $4 \leq 0 + \min(3,1) + \min(3,1) + \min(2,1) + \min(2,1) = 4$ ✓. For $k=2$ : $7 \leq 2 + \min(3,2) + \min(2,2) + \min(2,2) = 8$ ✓. Continuing for all $k$ verifies this is graphical. One realization is $K_5$ with one edge removed.

Remark

The Havel-Hakimi algorithm provides a constructive procedure: repeatedly connect the highest-degree vertex to the next $d_1$ highest-degree vertices, then recurse. This algorithm runs in $O(n^2)$ time and either constructs a realization or determines none exists.

TheoremErdős-Gallai Corollary

A sequence is graphical if and only if applying the Havel-Hakimi reduction eventually produces the all-zeros sequence without any negative entries.

Understanding degree sequences is essential for graph generation, network modeling, and extremal graph theory. The Erdős-Gallai theorem elegantly connects local vertex properties (degrees) to global graph existence.