Robertson–Seymour theorem
In graph theory, the Robertson-Seymour theorem states that every "downwardly closed" set of (isomorphism classes of) finite graphs is precisely the set of all (isomorphism classes of) graphs that lack a certain set of finitely many "forbidden minors." In order that the reader can understand this, we need certain definitions:
- A graph H is a minor of a graph G if H can be made from G by deleting or contracting edges.
- A downwardly closed set of isomorphism classes of graphs is a set S such that if G ε S and H is a minor of G, then H ε S.
Examples:
- The set of all planar graphs is downwardly closed.
- The set of all outer planar graphs is downwardly closed. Those are the graphs that can be embedded in a plane with all vertices lying on a circle and all edges lying in the enclosed disk.
- The set of all graphs that are knotlessly embeddable in Euclidean 3-space is downwardly closed.
- The set of all graphs that are knotlessly embeddable in Euclidean 3-space is downwardly closed.
[More examples should be added.]
Kuratowski's theorem states that a graph is planar if and only if it has no minor isomorphic either to K5, the complete graph on five vertices, or K3,3, the complete bipartite graph in which each part has three vertices. Those two graphs are the "forbidden minors" for the set of all planar graphs. It is readily seen that every downwardly closed set is characterized by its class of forbidden minors. The Robertson-Seymour theorem says that for every downwardly closed set, the class of forbidden minors is finite.
[Here the set of forbidden minors for the family of outer planar graphs should be added, and the set of forbidden minors for the family of knotlessly embeddable graphs, and other examples.]