# Robertson–Seymour theorem

The **Robertson–Seymour theorem** (also called the Graph Minors Theorem) states that finite graphs are well-quasi-ordered by the minor relation: in every infinite set of finite graphs, one of the graphs is isomorphic to a minor of another. [Neil Robertson](https://www.edgepedia.org/neil-robertson) and [Paul Seymour](https://www.edgepedia.org/paul-seymour-mathematician) proved it across a series of papers titled *Graph Minors*, published from 1983 to 2004 in the *Journal of Combinatorial Theory, Series B*.<sup>[1](https://www.jstage.jst.go.jp/article/iis/17/3/17_3_197/_pdf)</sup><sup> • </sup><sup>[2](https://doi.org/10.1090/noti2733)</sup>

| Key fact | Detail |
|---|---|
| Statement | In any infinite set of finite graphs, there are two graphs one of which is isomorphic to a minor of the other; equivalently, the minor order is a well-quasi-order<sup>[3](https://escholarship.mcgill.ca/downloads/qf85nh23t)</sup> |
| Origin | Proved as Wagner's conjecture, posed by K. Wagner, over a series of papers in the *Journal of Combinatorial Theory, Series B* from 1983 to 2004<sup>[1](https://www.jstage.jst.go.jp/article/iis/17/3/17_3_197/_pdf)</sup> |
| Forbidden-minor consequence | Every minor-closed class of graphs is characterized by finitely many forbidden minors, a vast generalization of the planar-graph case<sup>[2](https://doi.org/10.1090/noti2733)</sup> |
| Algorithmic consequence | The series yields an algorithm for the Minor Checking problem running in time f(h)·n, where h is the order of the sought minor H and f is some function of h<sup>[4](https://www.sciencedirect.com/science/article/pii/S0095895623000175)</sup> |
| Key intermediate results | Graphs of large tree-width contain large grid minors, and graphs of bounded tree-width are well-quasi-ordered<sup>[5](https://users.fmf.uni-lj.si/mohar/Papers/Bcc2001.pdf)</sup> |
| Logical strength | The theorem's proof strength has been analyzed via the ordinal analysis of the system \( (\Pi^{1}_{1}\text{-}\mathsf{CA})_{0} \)<sup>[2](https://doi.org/10.1090/noti2733)</sup> |

## Background: minors and Wagner's conjecture

[A minor](https://www.edgepedia.org/a-minor) of a graph G is a graph obtainable from G by deleting edges and vertices and contracting edges. The minor relation orders graphs by how their connectivity is arranged, and a class of graphs is minor-closed when every minor of a member is again a member.

K. Wagner conjectured that if \( G_{1}, G_{2}, \ldots \) is any countable sequence of finite graphs, then there exist indices \( i, j \) with \( j > i \geq 1 \) such that \( G_{i} \) is isomorphic to a minor of \( G_{j} \).<sup>[6](https://www.sciencedirect.com/science/article/pii/009589569090120O)</sup> A well-quasi-order is an ordering in which every infinite sequence contains an increasing pair, so the conjecture says exactly that finite graphs are well-quasi-ordered by minors.<sup>[3](https://escholarship.mcgill.ca/downloads/qf85nh23t)</sup>

A partial precedent existed. [Joseph Kruskal](https://www.edgepedia.org/joseph-kruskal) had proved that trees are well-quasi-ordered, so Wagner's conjecture held when all the graphs \( G_{i} \) are trees.<sup>[6](https://www.sciencedirect.com/science/article/pii/009589569090120O)</sup>

## The proof campaign

Robertson and Seymour proved the conjecture incrementally rather than in one step. Their paper *Graph Minors. IV. Tree-width and well-quasi-ordering* (1990) extended Kruskal's theorem to all sequences in which the first member \( G_{1} \) is planar, and stated the intention to prove the general conjecture in a future paper, for which the results of that paper would be needed.<sup>[6](https://www.sciencedirect.com/science/article/pii/009589569090120O)</sup> The same paper introduced tree-width, a decomposition measure that became one of the central tools of the series.<sup>[6](https://www.sciencedirect.com/science/article/pii/009589569090120O)</sup>

Two structural results carried much of the argument. One is the grid theorem: graphs of large tree-width contain large grid minors, so excluding a fixed grid bounds the tree-width of a graph.<sup>[5](https://users.fmf.uni-lj.si/mohar/Papers/Bcc2001.pdf)</sup> The other is the well-quasi-ordering of graphs of bounded tree-width.<sup>[5](https://users.fmf.uni-lj.si/mohar/Papers/Bcc2001.pdf)</sup> Together these reduce the ordering question for a minor-closed class to graphs of controlled decomposition.<sup>[5](https://users.fmf.uni-lj.si/mohar/Papers/Bcc2001.pdf)</sup>

**Later papers in the series.** *Graph Minors. XVI. Excluding a non-planar graph* (2003) contains what its authors call the cornerstone theorem of the series, describing the structure of graphs with no minor isomorphic to a given graph.<sup>[7](https://doi.org/10.1016/s0095-8956%2803%2900042-x)</sup> *Graph Minors. XVIII. Tree-decompositions and well-quasi-ordering* (2003) combined two earlier results into a lemma: if each member of a class has a linked tree-decomposition into well-behaved pieces, the class is well-quasi-ordered by minors, and for every finite graph G there is a linked tree-decomposition into pieces corresponding to the large-order tangles of G.<sup>[8](https://doi.org/10.1016/S0095-8956%2803%2900067-4)</sup> *Graph Minors. XIX. Well-quasi-ordering on a surface* (2004) extended the 1990 surface result from graphs to hypergraphs drawn in a fixed surface, with edges labeled from a well-quasi-order that the minor relation must respect.<sup>[9](https://www.sciencedirect.com/science/article/pii/S0095895603001047)</sup>

## Consequences

**Finite forbidden minors.** The excluded minors of a minor-closed class form an antichain under the minor order, so the Robertson–Seymour theorem implies there can only be finitely many of them.<sup>[10](https://doi.org/10.1016/j.disc.2004.07.039)</sup> Equivalently, any minor-closed class of graphs can be characterized by finitely many forbidden minors, a vast generalization of the planar case, where Kuratowski-type obstruction sets have exactly two members.<sup>[2](https://doi.org/10.1090/noti2733)</sup><sup> • </sup><sup>[1](https://www.jstage.jst.go.jp/article/iis/17/3/17_3_197/_pdf)</sup>

**Algorithms.** The seminal algorithmic result of the series is an algorithm solving the Minor Checking problem, deciding whether an input graph on n vertices contains a fixed graph H as a minor, in time f(h)·n, where h is the order of H and f is some function of h.<sup>[4](https://www.sciencedirect.com/science/article/pii/S0095895623000175)</sup> Because the theorem makes every minor-closed property decidable by finitely many minor tests, this gives a polynomial-time algorithm for any such property whose forbidden minors are known.<sup>[2](https://doi.org/10.1090/noti2733)</sup>

**Structure theory.** According to the Graph Minors Structure Theorem, every graph H excluded as a minor imposes a tree-decomposition of bounded adhesion on H-minor-free graphs, in which each bag can be drawn on a surface that cannot accommodate H once a few apex vertices are deleted and some vertices are grouped into a limited quantity of vortices of bounded depth.<sup>[11](https://arxiv.org/abs/2306.01724)</sup> Related work in the series includes the finiteness, for each fixed surface S, of the set of minimal forbidden minors for embedding in S.<sup>[5](https://users.fmf.uni-lj.si/mohar/Papers/Bcc2001.pdf)</sup>

## Logical strength

The theorem is strong in the sense of mathematical logic. Its proof-theoretic analysis connects it to the system \( (\Pi^{1}_{1}\text{-}\mathsf{CA})_{0} \): the Graph Minors Theorem proves the well-orderedness of that system's ordinal, and this is the source of its independence results.<sup>[2](https://doi.org/10.1090/noti2733)</sup> Subsequent work has investigated upper bounds for the proof strength of the theorem.<sup>[2](https://doi.org/10.1090/noti2733)</sup>

## References

1. [Theorem 3.11 (Robertson and Seymour 1983–2004), Interdisciplinary Information Sciences 17(3), 197–216 (2011)](https://www.jstage.jst.go.jp/article/iis/17/3/17_3_197/_pdf)
2. [Theorem 9.1 (Robertson and Seymour 1986–2004), Notices of the American Mathematical Society](https://doi.org/10.1090/noti2733)
3. [Robertson and Seymour proved that any infinite sequence of finite graphs must have one graph that is a proper minor of another, McGill eScholarship](https://escholarship.mcgill.ca/downloads/qf85nh23t)
4. [k-apices of minor-closed graph classes. I. Bounding the obstructions, Journal of Combinatorial Theory, Series B](https://www.sciencedirect.com/science/article/pii/S0095895623000175)
5. [Excluded minors for a fixed surface (Bcc2001), Bojan Mohar](https://users.fmf.uni-lj.si/mohar/Papers/Bcc2001.pdf)
6. [Graph minors. IV. Tree-width and well-quasi-ordering, Journal of Combinatorial Theory, Series B 48(2), 227–254 (1990)](https://www.sciencedirect.com/science/article/pii/009589569090120O)
7. [Graph Minors. XVI. Excluding a non-planar graph, Journal of Combinatorial Theory, Series B](https://doi.org/10.1016/s0095-8956%2803%2900042-x)
8. [Graph Minors. XVIII. Tree-decompositions and well-quasi-ordering, Journal of Combinatorial Theory, Series B 89(1), 77–108 (2003)](https://doi.org/10.1016/S0095-8956%2803%2900067-4)
9. [Graph Minors. XIX. Well-quasi-ordering on a surface, Journal of Combinatorial Theory, Series B 90(2), 325–385 (2004)](https://www.sciencedirect.com/science/article/pii/S0095895603001047)
10. [Recent work in matroid representation theory, Discrete Mathematics](https://doi.org/10.1016/j.disc.2004.07.039)
11. [Excluding Surfaces as Minors in Graphs, arXiv:2306.01724](https://arxiv.org/abs/2306.01724)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph theory subfields and named results › Structural and graph minor theory*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license