ErdsGallai

The Erdős–Gallai theorem provides a complete characterization of which degree sequences can be realized as simple graphs. It was introduced by Paul Erdős and T. Gallai in 1960 and remains a foundational result in graph theory, with applications to network reconstruction and degree sequence testing.

Let d1 ≥ d2 ≥ ... ≥ dn be a sequence of nonnegative integers with even sum. The sequence is graphical, meaning there exists a simple graph with exactly those vertex degrees, if and only if for every k in {1, 2, ..., n} the inequality

sum_{i=1}^k d_i ≤ k(k − 1) + sum_{i=k+1}^n min(d_i, k)

holds. The evenness of the total sum is necessary because it equals twice the number of edges in any graph. The right-hand side of the inequality represents the maximum number of edges that can connect the first k vertices to the rest, given their degree constraints.

Consequences and context: the theorem provides a finite set of inequalities to test graphicality, enabling polynomial-time verification after sorting the sequence. It is closely related to the Havel–Hakimi algorithm, which offers a constructive method to realize a graphical sequence. The Erdős–Gallai result also connects to concepts of majorization and graphical partitions and has been extended to variants such as directed graphs and multigraphs.

See also: Havel–Hakimi algorithm; graphical degree sequence; majorization in graph theory. References: Erdős, P.; Gallai, T. On graphs with given degrees (1960).