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
In Branch
Proved By
Sources
1. Erdos-Gallai Theorem (Wikipedia)
Wikimedia FoundationLead sectionQuote, Lead section
The theorem was published in 1960 by Paul Erdős 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.