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 Erdos-Gallai Theorem
Filter Results2 entries
Connections
Has Statement Form
In Branch
Principal Result Of
Source Erdos-Gallai Theorem (Wikipedia)
Source Erdos-Gallai Theorem (Wikipedia)
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.
Erdos-Gallai Theorem (Wikipedia)
Principal Result Of: Paul Erdos, Lead sentence of the article on the result
The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named.
Principal Result Of: Tibor Gallai, Lead sentence of the article on the result
The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named.
View the SourceReader 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.