Robertson–Seymour theorem
Encyclopedia
In graph theory
, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor
relationship, form a well-quasi-ordering
. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graph
s as being the graphs that do not have the complete graph
K5 and the complete bipartite graph
K3,3 as minors.
The Robertson–Seymour theorem is named after mathematicians Neil Robertson
and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004. Before its proof, the statement of the theorem was known as Wagner's conjecture after the German mathematician Klaus Wagner
, although Wagner said he never conjectured it.
A weaker result for trees
is implied by Kruskal's tree theorem
, which was conjectured in 1937 by Andrew Vázsonyi and proved in 1960 independently by Joseph Kruskal
and S. Tarkowski.
of an undirected graph G is any graph that may be obtained from G by a sequence of zero or more contractions of edges of G and deletions of edges and vertices of G. The minor relationship forms a partial order on the set of all distinct finite undirected graphs, as it obeys the three axioms of partial orders: it is reflexive
(every graph is a minor of itself), transitive
(a minor of a minor of G is itself a minor of G), and antisymmetric
(if two graphs G and H are minors of each other, then they must be isomorphic
). However, if graphs that are isomorphic may nonetheless be considered as distinct objects, then the minor ordering on graphs forms a preorder
, a relation that is reflexive and transitive but not necessarily antisymmetric.
A preorder is said to form a well-quasi-ordering
if it contains neither an infinite descending chain
nor an infinite antichain
. For instance, the usual ordering on the non-negative integers is a well-quasi-ordering, but the same ordering on the set of all integers is not, because it contains the infinite descending chain 0, −1, −2, −3...
The Robertson–Seymour theorem states that finite undirected graphs and graph minors form a well-quasi-ordering. It is obvious that the graph minor relationship does not contain any infinite descending chain, because each contraction or deletion reduces the number of edges and vertices of the graph (a non-negative integer). The nontrivial part of the theorem is that there are no infinite antichains, infinite sets of graphs that are all unrelated to each other by the minor ordering. If S is a set of graphs, and M is a subset of S containing one representative graph for each equivalence class of minimal elements (graphs that belong to S but for which no proper minor belongs to S), then M forms an antichain; therefore, an equivalent way of stating the theorem is that, in any infinite set S of graphs, there must be only a finite number of non-isomorphic minimal elements.
Another equivalent form of the theorem is that, in any infinite set S of graphs, there must be a pair of graphs one of which is a minor of the other. The statement that every infinite set has finitely many minimal elements implies this form of the theorem, for if there are only finitely many minimal elements, then each of the remaining graphs must belong to a pair of this type with one of the minimal elements. And in the other direction, this form of the theorem implies the statement that there can be no infinite antichains, because an infinite antichain is a set that does not contain any pair related by the minor relation.
under the operation of taking minors if every minor of a graph in F also belongs to F. If F is a minor-closed family, then let S be the set of graphs that are not in F (the complement
of F). According to the Robertson–Seymour theorem, there exists a finite set H of minimal elements in S. These minimal elements form a forbidden graph characterization of F: the graphs in F are exactly the graphs that do not have any graph in H as a minor. The members of H are called the excluded minors (or forbidden minors, or minor-minimal obstructions) for the family F.
For example, the planar graph
s are closed under taking minors: contracting an edge in a planar graph, or removing edges or vertices from the graph, cannot destroy its planarity. Therefore, the planar graphs have a forbidden minor characterization, which in this case is given by Wagner's theorem: the set H of minor-minimal nonplanar graphs contains exactly two graphs, the complete graph
K5 and the complete bipartite graph
K3,3, and the planar graphs are exactly the graphs that do not have a minor in the set {K5, K3,3}.
The existence of forbidden minor characterizations for all minor-closed graph families is an equivalent way of stating the Robertson–Seymour theorem. For, suppose that every minor-closed family F has a finite set H of minimal forbidden minors, and let S be any infinite set of graphs. Define F from S as the family of graphs that do not have a minor in S. Then F is minor-closed and the finite set H of minimal forbidden minors in F must be exactly the minimal elements in S, so S must have only a finite number of minimal elements.
graph (or, if one restricts to simple graph
s, the cycle with three vertices). This means that a graph is a forest if and only if none of its minors is the loop (or, the cycle with three vertices, respectively). The sole obstruction for the set of paths is the tree with four vertices, one of which has degree 3. In these cases, the obstruction set contains a single element, but in general this is not the case. Wagner's theorem states that a graph is planar if and only if it has neither K5 nor K3,3 as a minor. In other words, the set {K5, K3,3} is an obstruction set for the set of all planar graphs, and in fact the unique minimal obstruction set. A similar theorem states that K4 and K2,3 are the forbidden minors for the set of outerplanar graphs.
Although the Robertson–Seymour theorem extends these results to arbitrary minor-closed graph families, it is not a complete substitute for these results, because it does not provide an explicit description of the obstruction set for any family. For example, it tells us that the set of toroidal graph
s has a finite obstruction set, but it does not provide any such set. The complete set of forbidden minors for toroidal graphs remains unknown, but contains at least 16000 graphs.
However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm. In many specific cases, checking whether a graph is in a given minor-closed family can be done more efficiently: for example, checking whether a graph is planar can be done in linear time.
However, this method does not directly provide a single fixed-parameter-tractable algorithm for computing the parameter value for a given graph with unknown k, because of the difficulty of determining the set of forbidden minors. Additionally, the large constant factors involved in these results make them highly impractical. Therefore, the development of explicit fixed-parameter algorithms for these problems, with improved dependence on k, has continued to be an important line of research.
by being unprovable in various formal systems that are much stronger than Peano arithmetic, yet being provable in systems much weaker than ZFC:
(Here, the size of a graph is the total number of its nodes and edges, and ≤ denotes the minor ordering.)
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor
Minor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
relationship, form a well-quasi-ordering
Well-quasi-ordering
In mathematics, specifically order theory, a well-quasi-ordering or wqo is a well-founded quasi-ordering with an additional restriction on sequences - that there is no infinite sequence x_i with x_i \not \le x_j for all i...
. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s as being the graphs that do not have the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K5 and the complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
K3,3 as minors.
The Robertson–Seymour theorem is named after mathematicians Neil Robertson
Neil Robertson (mathematician)
G. Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor at the Ohio State University. He earned his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. According to the criteria of the Erdős Number...
and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004. Before its proof, the statement of the theorem was known as Wagner's conjecture after the German mathematician Klaus Wagner
Klaus Wagner (mathematician)
Klaus Wagner was a German mathematician. He studied topology at the University of Cologne under the supervision of Karl Dörge, who had been a student of Issai Schur. Wagner received his Ph.D. in 1937, and taught at Cologne for many years himself...
, although Wagner said he never conjectured it.
A weaker result for trees
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
is implied by Kruskal's tree theorem
Kruskal's tree theorem
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered...
, which was conjectured in 1937 by Andrew Vázsonyi and proved in 1960 independently by Joseph Kruskal
Joseph Kruskal
Joseph Bernard Kruskal, Jr. was an American mathematician, statistician, computer scientist and psychometrician. He was a student at the University of Chicago and at Princeton University, where he completed his Ph.D. in 1954, nominally under Albert W...
and S. Tarkowski.
Statement
A minorMinor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
of an undirected graph G is any graph that may be obtained from G by a sequence of zero or more contractions of edges of G and deletions of edges and vertices of G. The minor relationship forms a partial order on the set of all distinct finite undirected graphs, as it obeys the three axioms of partial orders: it is reflexive
Reflexive relation
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
(every graph is a minor of itself), transitive
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
(a minor of a minor of G is itself a minor of G), and antisymmetric
Antisymmetric relation
In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,...
(if two graphs G and H are minors of each other, then they must be isomorphic
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
). However, if graphs that are isomorphic may nonetheless be considered as distinct objects, then the minor ordering on graphs forms a preorder
Preorder
In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...
, a relation that is reflexive and transitive but not necessarily antisymmetric.
A preorder is said to form a well-quasi-ordering
Well-quasi-ordering
In mathematics, specifically order theory, a well-quasi-ordering or wqo is a well-founded quasi-ordering with an additional restriction on sequences - that there is no infinite sequence x_i with x_i \not \le x_j for all i...
if it contains neither an infinite descending chain
Infinite descending chain
Given a set S with a partial order ≤, an infinite descending chain is a chain V that is a subset of S upon which ≤ defines a total order such that V has no least element, that is, an element m such that for all elements n in V it holds that m ≤ n.As an example, in the set of integers, the chain...
nor an infinite antichain
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
. For instance, the usual ordering on the non-negative integers is a well-quasi-ordering, but the same ordering on the set of all integers is not, because it contains the infinite descending chain 0, −1, −2, −3...
The Robertson–Seymour theorem states that finite undirected graphs and graph minors form a well-quasi-ordering. It is obvious that the graph minor relationship does not contain any infinite descending chain, because each contraction or deletion reduces the number of edges and vertices of the graph (a non-negative integer). The nontrivial part of the theorem is that there are no infinite antichains, infinite sets of graphs that are all unrelated to each other by the minor ordering. If S is a set of graphs, and M is a subset of S containing one representative graph for each equivalence class of minimal elements (graphs that belong to S but for which no proper minor belongs to S), then M forms an antichain; therefore, an equivalent way of stating the theorem is that, in any infinite set S of graphs, there must be only a finite number of non-isomorphic minimal elements.
Another equivalent form of the theorem is that, in any infinite set S of graphs, there must be a pair of graphs one of which is a minor of the other. The statement that every infinite set has finitely many minimal elements implies this form of the theorem, for if there are only finitely many minimal elements, then each of the remaining graphs must belong to a pair of this type with one of the minimal elements. And in the other direction, this form of the theorem implies the statement that there can be no infinite antichains, because an infinite antichain is a set that does not contain any pair related by the minor relation.
Forbidden minor characterizations
A family F of graphs is said to be closedClosure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under the operation of taking minors if every minor of a graph in F also belongs to F. If F is a minor-closed family, then let S be the set of graphs that are not in F (the complement
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
of F). According to the Robertson–Seymour theorem, there exists a finite set H of minimal elements in S. These minimal elements form a forbidden graph characterization of F: the graphs in F are exactly the graphs that do not have any graph in H as a minor. The members of H are called the excluded minors (or forbidden minors, or minor-minimal obstructions) for the family F.
For example, the planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s are closed under taking minors: contracting an edge in a planar graph, or removing edges or vertices from the graph, cannot destroy its planarity. Therefore, the planar graphs have a forbidden minor characterization, which in this case is given by Wagner's theorem: the set H of minor-minimal nonplanar graphs contains exactly two graphs, the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K5 and the complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
K3,3, and the planar graphs are exactly the graphs that do not have a minor in the set {K5, K3,3}.
The existence of forbidden minor characterizations for all minor-closed graph families is an equivalent way of stating the Robertson–Seymour theorem. For, suppose that every minor-closed family F has a finite set H of minimal forbidden minors, and let S be any infinite set of graphs. Define F from S as the family of graphs that do not have a minor in S. Then F is minor-closed and the finite set H of minimal forbidden minors in F must be exactly the minimal elements in S, so S must have only a finite number of minimal elements.
Examples of minor-closed families
The following sets of finite graphs are minor-closed, and therefore (by the Robertson–Seymour theorem) have forbidden minor characterizations:- forests, linear forests (disjoint unionDisjoint unionIn mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , a disjoint union...
s of path graphPath graphIn the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
s), pseudoforestPseudoforestIn graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be...
s, and cactus graphCactus graphIn graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph belongs to at most one simple cycle. Equivalently, every block is an edge or a cycle.-Properties:Cacti are outerplanar graphs...
s; - planar graphPlanar graphIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s, outerplanar graphOuterplanar graphIn graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
s, apex graphApex graphIn graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. We say an apex, not the apex because an apex graph may have more than one apex...
s (formed by adding a single vertex to a planar graph), toroidal graphToroidal graphIn mathematics, a graph G is toroidal if it can be embedded on the torus. In other words, the graph's vertices can be placed on a torus such that no edges cross...
s, and the graphs that can be embeddedGraph embeddingIn topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
on any fixed two-dimensional manifoldManifoldIn mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....
; - graphs that are linklessly embeddableLinkless embeddingIn topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph have nonzero linking number. A flat embedding is an embedding with the property that every cycle is the...
in Euclidean 3-space, and graphs that are knotlesslyKnot (mathematics)In mathematics, a knot is an embedding of a circle in 3-dimensional Euclidean space, R3, considered up to continuous deformations . A crucial difference between the standard mathematical and conventional notions of a knot is that mathematical knots are closed—there are no ends to tie or untie on a...
embeddable in Euclidean 3-space; - graphs with a feedback vertex setFeedback vertex setIn the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph....
of size bounded by some fixed constant; graphs with Colin de Verdière graph invariantColin de Verdière graph invariantColin de Verdière's invariant is a graph parameter \mu for any graph G introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.-Definition:...
bounded by some fixed constant; graphs with treewidth, pathwidth, or branchwidth bounded by some fixed constant.
Obstruction sets
Some examples of finite obstruction sets were already known for specific classes of graphs before the Robertson–Seymour theorem was proved. For example, the obstruction for the set of all forests is the loopGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
graph (or, if one restricts to simple graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
s, the cycle with three vertices). This means that a graph is a forest if and only if none of its minors is the loop (or, the cycle with three vertices, respectively). The sole obstruction for the set of paths is the tree with four vertices, one of which has degree 3. In these cases, the obstruction set contains a single element, but in general this is not the case. Wagner's theorem states that a graph is planar if and only if it has neither K5 nor K3,3 as a minor. In other words, the set {K5, K3,3} is an obstruction set for the set of all planar graphs, and in fact the unique minimal obstruction set. A similar theorem states that K4 and K2,3 are the forbidden minors for the set of outerplanar graphs.
Although the Robertson–Seymour theorem extends these results to arbitrary minor-closed graph families, it is not a complete substitute for these results, because it does not provide an explicit description of the obstruction set for any family. For example, it tells us that the set of toroidal graph
Toroidal graph
In mathematics, a graph G is toroidal if it can be embedded on the torus. In other words, the graph's vertices can be placed on a torus such that no edges cross...
s has a finite obstruction set, but it does not provide any such set. The complete set of forbidden minors for toroidal graphs remains unknown, but contains at least 16000 graphs.
Polynomial time recognition
The Robertson–Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph G, there is a polynomial time algorithm for testing whether larger graphs have G as a minor. The running time of this algorithm can be expressed as a cubic polynomial in the size of the larger graph (although there is a constant factor in this polynomial that depends superpolynomially on the size of G). As a result, for every minor-closed family F, there is polynomial time algorithm for testing whether a graph belongs to F: simply check, for each of the forbidden minors for F, whether the given graph contains that forbidden minor.However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm. In many specific cases, checking whether a graph is in a given minor-closed family can be done more efficiently: for example, checking whether a graph is planar can be done in linear time.
Fixed-parameter tractability
For graph invariants with the property that, for each k, the graphs with invariant at most k are minor-closed, the same method applies. For instance, by this result, treewidth, branchwidth, and pathwidth, vertex cover, and the minimum genus of an embedding are all amenable to this approach, and for any fixed k there is a polynomial time algorithm for testing whether these invariants are at most k, in which the exponent in the running time of the algorithm does not depend on k. A problem with this property, that it can be solved in polynomial time for any fixed k with an exponent that does not depend on k, is known as fixed-parameter tractable.However, this method does not directly provide a single fixed-parameter-tractable algorithm for computing the parameter value for a given graph with unknown k, because of the difficulty of determining the set of forbidden minors. Additionally, the large constant factors involved in these results make them highly impractical. Therefore, the development of explicit fixed-parameter algorithms for these problems, with improved dependence on k, has continued to be an important line of research.
Finite form of the graph minor theorem
showed that the following theorem exhibits the independence phenomenonIndependence (mathematical logic)
In mathematical logic, independence refers to the unprovability of a sentence from other sentences.A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that...
by being unprovable in various formal systems that are much stronger than Peano arithmetic, yet being provable in systems much weaker than ZFC:
- Theorem: For every positive integer n, there is an integer m so large that if G1, ..., Gm is a sequence of finite undirected graphs,
- where each Gi has size at most n+i, then Gj ≤ Gk for some j < k.
(Here, the size of a graph is the total number of its nodes and edges, and ≤ denotes the minor ordering.)