The Erdos-Gallai Theorem gives a necessary and sufficient condition for a finite sequence of non-negative integers to be the degree sequence of some simple graph. Proved by Paul Erdos and Tibor Gallai, it is a basic result in graph theory used to determine whether a proposed sequence of vertex degrees can actually be realized by an actual graph.
Facts
StatementA finite sequence of natural numbers is the degree sequence of some simple graph if and only if the sequence sums to an even number and satisfies a family of inequalities bounding the sum of its largest terms against its remaining terms. Paul Erdos and Tibor Gallai published the theorem in 1960. 1 Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Proved By
Sources
1. Erdos-Gallai Theorem (Wikipedia)
Wikimedia Foundationlead section, first paragraphQuote, lead section, first paragraph
The Erdos-Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph. A sequence obeying these conditions is called "graphic". The theorem was published in 1960 by Paul Erdos and Tibor Gallai, after whom it is named.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.