Robertson–Seymour theorem

Remarks

An equivalent form: let $\mathcal{C}$ be a class of finite graphs closed under isomorphism and under taking minors. Then there is a finite set $\mathcal{F}$ of graphs such that a graph lies in $\mathcal{C}$ if and only if no member of $\mathcal{F}$ is a minor of it. For planar graphs $\mathcal{F} = \set{K_5, K_{3,3}}$, by Wagner's theorem, and for forests $\mathcal{F} = \set{K_3}$. Neil Robertson and Paul Seymour proved the theorem in a long series of papers called Graph Minors, published between 1983 and 2004. The proof rests on a structure theorem for graphs that exclude a fixed minor, built on tree decompositions and embeddings in surfaces. The same project gives a polynomial-time algorithm that tests whether a fixed graph $H$ is a minor of an input graph. So every minor-closed class can be recognized in polynomial time. This proof of polynomial-time recognition is not constructive, since the theorem does not say how to find the set $\mathcal{F}$.

Going deeper

For a student

For trees, the analogous statement is Kruskal's tree theorem. The proof of the general case extends ideas from it through treewidth. Graphs of bounded treewidth are handled like trees, and graphs of large treewidth contain large grid minors. The theorem is one of the deepest results of combinatorics and gives finite obstruction sets for embeddability in any fixed surface.