bestätigt die Vermutung von Wagner (Wagner, Vermutung von) und sagt aus, daß es für jede unendliche Folge G₁, G₂,…von Graphen Indizes i < j so gibt, daß G_i ein Minor (Minor eines Graphen) von G_j ist.

Definiert man eine Relation „≤“ auf der Menge aller Graphen dadurch, daß G ≤ G′ genau dann gilt, wenn G ein Minor von G′ ist, dann sagt der Satz von Robertson-Seymour aus, daß ≤ eine WohlQuasi-Ordnung auf der Menge aller Graphen ist.

Der Beweis dieses Satzes ist in einer Reihe von über 20 Artikeln von N. Robertson und P. Seymour unter dem Namen „graph-minor-project“ enthalten, die seit 1983 in einem Zeitraum von über 15 Jahren erschienen sind, und zählt zu den schwierigsten und tiefsten Beweisen in der Graphentheorie. Seine Autoren entwickelten für ihn die Theorie der Minoren und Baumweite von Graphen.

Weitere wichtige Ergebnisse dieser Theorie sind z. B. folgende Aussagen: