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. To understand this statement, 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 S of isomorphism classes of graphs is a set such that if G ∈ S and H is a minor of G, then H ∈ S.
Examples (all graphs are taken to be finite):
- The set of all graphs that are disjoint unions of paths is downwardly closed.
- The set of all forests is downwardly closed. A forest is a graph that has no cycles.
- The set of all planar graphs is downwardly closed.
- The set of all outerplanar 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 can be embedded without edge intersections in a torus is downwardly closed.
- More generally, given any surface S, the set of all graphs that can be embedded without edge intersections in S is downwardly closed.
- The set of all graphs that are knotlessly embeddable in Euclidean 3-space is downwardly closed.
- The set of all graphs that are linklessly embeddable in Euclidean 3-space is downwardly closed.
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 has 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.