Erdős–Gallai theorem (degree sequences)

The Erdős–Gallai theorem characterizes which nonincreasing sequences of nonnegative integers are degree sequences of simple graphs through parity and a family of inequalities.

Degree sequence: A list of vertex degrees associated with a graph. The theorem decides whether a proposed list can come from a simple graph.
Paul Erdős: A Hungarian mathematician known for extensive work in combinatorics, number theory, and probability. He co-authored the degree-sequence criterion bearing his name.
Graph realization: The construction of a graph whose vertices have a prescribed degree sequence. The theorem certifies whether such a construction is possible.
Fulkerson–Chen–Anstee theorem: A characterization of bipartite degree sequences through inequalities on the two vertex classes. It is the bipartite counterpart to characterizing degree sequences of simple graphs.
Handshaking lemma: The result that the sum of graph vertex degrees equals twice the number of edges. It yields the theorem’s necessary even-sum condition.
Tibor Gallai: A Hungarian mathematician whose work included graph theory and combinatorial optimization. He co-authored the theorem independently of Erdős.
Network science: The study of networks using mathematical and computational methods. Degree sequences summarize connectivity patterns that network models seek to reproduce.
Gale–Ryser theorem: A criterion determining whether two integer sequences are the degree lists of the two parts of a bipartite graph. It characterizes bipartite realizability rather than unrestricted simple-graph realizability.
Majorization: A partial order comparing vectors through their sorted partial sums. The inequalities constrain degree prefixes against the remaining degree totals.
Havel–Hakimi theorem: A characterization stating that a nonincreasing sequence is graphical exactly when a sequence formed by reducing its largest entry is graphical. This earlier recursive criterion addresses the same graphical-sequence problem.

Linked from 1 page

Degree (graph theory)Related: It tests whether proposed local degrees can belong to one simple graph.