Theorem

Robertson-Seymour Theorem

Combinatorics and Graph Theory

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

Statement

The 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

Proof Year

2004 1

Classification

Statement Form

Characterization Theorem 1

Connections

Source Robertson-Seymour Theorem (Wikipedia)

Paul Seymour

Source Robertson-Seymour Theorem (Wikipedia)

Sources

1. Robertson-Seymour Theorem (Wikipedia)

Wikimedia Foundation

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.
Proved By: Neil Robertson, Lead section
The Robertson-Seymour theorem is named after mathematicians Neil Robertson and Paul D.
Proved By: Paul Seymour, Lead section
The Robertson-Seymour theorem is named after mathematicians Neil Robertson and Paul D.
In Group: Graph Theory, Lead section
In graph theory, the Robertson-Seymour theorem (also called the

Switch Atlas

The Inner World

The Civil World

The Natural World

Robertson-Seymour Theorem

Has Statement Form

In Branch

Proved By