The Robertson-Seymour Theorem states that the class of all finite graphs is well-quasi-ordered under the graph minor relation, meaning that in any infinite collection of graphs, some one graph in the collection is a minor of another. Proved by Neil Robertson and Paul Seymour across a long series of papers, it implies that every graph property closed under taking minors can be tested by checking for a finite list of forbidden minors, generalizing the Kuratowski and Wagner characterizations of planarity.
Facts
StatementThe Robertson-Seymour Theorem states that in any infinite collection of finite graphs, some graph is a minor of another, so the class of all finite graphs is well-quasi-ordered under the graph minor relation, and every family of graphs closed under taking minors can be characterized by a finite list of forbidden minors. 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
Sources
1. Robertson-Seymour Theorem (Wikipedia)
Wikimedia FoundationLead section, second paragraphQuote, Lead section, second paragraph
The Robertson-Seymour theorem is named after mathematicians Neil Robertson and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004.
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.