Main Page | See live article | Alphabetical index

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. The hard part is finiteness; if the words "finitely many" were deleted from the statement the theorem would become fairly trivial. In order that the reader can understand this, we need certain definitions:

Examples (all graphs are taken to be finite):

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 minimal set of forbidden minors is finite.

For example, for the set of forests, the forbidden minor is the cycle with three vertices. For the set of paths, the forbidden minor is the tree with four vertices, one of which having degree 3.

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. A similar theorem states that K4 and K2,3 are the forbidden minors for the outerplanar graphs.

The forbidden minors for the torus-embeddable graphs are not known. Robertson-Seymour's original proof of their theorem was not constructive (i.e. it did not give an upper bound for the size of the forbidden minors). Others have later proved upper bounds for the forbidden minors of S-embeddable graphs. These upper bounds depend on the genus of S and are humongous.