Erdős–Gallai theorem

Erdős–Gallai theorem
Name	Erdős–Gallai theorem
Field	Graph theory
Introduced	1960
Authors	Paul Erdős, Tibor Gallai

Erdős–Gallai theorem The Erdős–Gallai theorem gives necessary and sufficient conditions for a finite nonincreasing sequence of nonnegative integers to be the degree sequence of a simple undirected graph. It characterizes graphical sequences by a finite family of inequalities, linking combinatorial constructions to extremal constraints; the theorem plays a central role in graph theory, combinatorics, and discrete mathematics.

Statement

Let d = (d1 ≥ d2 ≥ ... ≥ dn) be a finite nonincreasing sequence of nonnegative integers. The Erdős–Gallai theorem states that d is graphical (i.e., is the degree sequence of a simple undirected graph on n vertices) if and only if the sum of the degrees is even and, for every k with 1 ≤ k ≤ n, the following inequality holds: sum_{i=1}^k di ≤ k(k−1) + sum_{i=k+1}^n min(di, k). This characterization reduces the existence question to checking at most n inequalities together with parity, yielding an exact combinatorial criterion.

History and context

The theorem was proved by Paul Erdős and Tibor Gallai in 1960, emerging from mid-20th-century developments in extremal graph theory, combinatorics, and the study of graph realizability problems. It built on earlier work by Havel and Hakimi concerning constructive procedures for degree sequences and complemented foundational contributions by Kőnig and Turán in graph structure. The result influenced later investigations in network theory, design theory, and algorithmic graph theory, intersecting with research by Frank Harary, Béla Bollobás, and László Lovász.

Proofs and methods

Proofs of the Erdős–Gallai theorem use combinatorial counting, induction, and constructive transformations. One classical approach transforms an instance by repeatedly applying the Havel–Hakimi algorithm—originally associated with Miklós Ruszinkó and historically attributed to Václav Havel and S. L. Hakimi—to reduce the sequence while preserving graphicality. Another proof employs double counting and the simple inequality sum_{i=1}^k di ≤ k(k−1)+ sum_{i=k+1}^n min(di,k), with the parity condition ensuring an even sum; such arguments resonate with techniques used by Paul Erdős in extremal combinatorics and by Tibor Gallai in decomposition theory. Algebraic and polyhedral perspectives relate the theorem to degree-constrained subgraph polytopes studied by Jack Edmonds and Éva Tardos, and analytic combinatorics approaches connect it to limit laws explored by Béla Bollobás and Oded Schramm.

Applications and consequences

The theorem is foundational for testing graphicality in network science, social network analysis, and bioinformatics when one must realize a prescribed degree sequence, linking to practical problems studied by Stanley and Ronald Graham. It underpins algorithms for constructing simple graphs with given degrees used in software by researchers around Jacco van Lint, Noga Alon, and Daniel Spielman. Consequences include characterizations of degree sequences of bipartite graphs via the Gale–Ryser theorem—connected historically to James Joseph Sylvester—and ties to the Erdős–Gallai inequalities being applied in studies by Paul Erdős on graphical enumeration and by Tibor Gallai on path decompositions. The theorem informs extremal results such as those by Turán and has implications for graphical realizability constraints appearing in work by Péter Frankl and Zoltán Füredi.

Examples and counterexamples

Examples illustrating the theorem include sequences like (3,3,2,2,2) and (3,3,3,1,0) which are tested by the inequalities and parity condition; small historical examples were discussed in expositions by Harary and Erdős. Counterexamples to naive sufficient conditions—such as a nonincreasing sequence with even sum but violating the k-inequalities—are classical pedagogical cases in textbooks by Douglas West and Jonathan Gross. Specific constructions exhibiting subtle failures of graphicality relate to extremal configurations studied by Turán and used as test cases in algorithmic validations by Béla Bollobás and László Lovász.

Generalizations and related results

Generalizations of the Erdős–Gallai theorem include characterizations for directed degree sequences (the Fulkerson–Chen–Anstee theorem and the Gale–Ryser theorem for bipartite matrices), degree-constrained subgraphs addressed by Jack Edmonds in matching theory, and criteria for pseudo-graphs and multigraphs explored by Harary and Hakimi. Related results comprise the Havel–Hakimi algorithm constructive method, polyhedral descriptions linked to Edmonds' matching polytope, and limit theorems for degree sequences developed in probabilistic combinatorics by Béla Bollobás, Svante Janson, and Oded Schramm. Extensions also touch on graphical sequences with forbidden subgraphs studied in extremal work by Paul Erdős, Péter Frankl, and Zoltán Füredi.

Category:Theorems in graph theory