graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Robertson–Seymour theorem (also called the graph minor theorem) states that the

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

s, partially ordered by the

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

relationship, form a

well-quasi-ordering In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements x_0, x_1, x_2, \ldots from X contains an increasing pair x_i \leq x_j with i x_2> \cdots) nor infinite seque ...

. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of

forbidden minor In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...

s, in the same way that

Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on five ...

characterizes the

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. In other words, it can be drawn in such a way that no edges cro ...

s as being the graphs that do not have the

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. A complete digraph is a directed graph in which every pair of distinct vertices is ...

''K''₅ or the

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..Electronic edition page 17. Graph theory i ...

''K''_3,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 Klaus Wagner (March 31, 1910 – February 6, 2000) was a German mathematician known for his contributions to graph theory. Education and career Wagner studied topology at the University of Cologne under the supervision of who had been a stude ...

, although Wagner said he never conjectured it. A weaker result for

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...

is implied by

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 under homeomorphic embedding. History The theorem was conjectured by Andrew Vázsonyi and proved b ...

, which was conjectured in 1937 by

Andrew Vázsonyi Andrew Vázsonyi (1916–2003), also known as Endre Weiszfeld and Zepartzatt Gozinto) was a Hungarian mathematician and operations researcher. He is known for Weiszfeld's algorithm for minimizing the sum of distances to a set of points, and for fo ...

and proved in 1960 independently by

Joseph Kruskal Joseph Bernard Kruskal, Jr. (; January 29, 1928 – September 19, 2010) was an American mathematician, statistician, computer scientist and psychometrician. Personal life Kruskal was born to a Jewish family in New York City to a successful fur ...

and S. Tarkowski.

Statement

A minor of an

''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 In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...

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 In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...

). However, if graphs that are isomorphic may nonetheless be considered as distinct objects, then the minor ordering on graphs forms a

preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...

, a relation that is reflexive and transitive but not necessarily antisymmetric. A preorder is said to form a

if it contains neither an infinite descending chain nor an infinite

antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wi ...

. 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... Another example is the set of positive integers ordered by divisibility, which has no infinite descending chains, but where the prime numbers constitute an infinite antichain. The Robertson–Seymour theorem states that finite undirected graphs and graph minors form a well-quasi-ordering. 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

closed Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...

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 class of graphs that are not in ''F'' (the

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...

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 In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...

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

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

: the set ''H'' of minor-minimal nonplanar graphs contains exactly two graphs, the

''K''₅ and the

''K''_3,3, and the planar graphs are exactly the graphs that do not have a minor in the set . 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 has a finite set ''H'' of minimal forbidden minors. Let ''C'' be the complement of ''F''. ''S'' is a subset of ''C'' since ''S'' and ''F'' are disjoint, and ''H'' are the minimal graphs in ''C''. Consider a graph ''G'' in ''H''. ''G'' cannot have a proper minor in ''S'' since ''G'' is minimal in ''C''. At the same time, ''G'' must have a minor in ''S'', since otherwise ''G'' would be an element in ''F''. Therefore, ''G'' is an element in ''S'', i.e., ''H'' is a subset of ''S'', and all other graphs in ''S'' have a minor among the graphs in ''H'', so ''H'' is the finite set of minimal elements of ''S''. For the other implication, assume that every set of graphs has a finite subset of minimal graphs and let a minor-closed set ''F'' be given. We want to find a set ''H'' of graphs such that a graph is in ''F'' if and only if it does not have a minor in ''H''. Let ''E'' be the graphs which are not minors of any graph in ''F'', and let ''H'' be the finite set of minimal graphs in ''E''. Now, let an arbitrary graph ''G'' be given. Assume first that ''G'' is in ''F''. ''G'' cannot have a minor in ''H'' since ''G'' is in ''F'' and ''H'' is a subset of ''E''. Now assume that ''G'' is not in ''F''. Then ''G'' is not a minor of any graph in ''F'', since ''F'' is minor-closed. Therefore, ''G'' is in ''E'', so ''G'' has a minor in ''H''.

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 A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...

, linear forests (

disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ( ...

s of

path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...

s), pseudoforests, and

cactus graph In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ...

s; *

s, outerplanar graphs, apex graphs (formed by adding a single vertex to a planar graph), toroidal graphs, and the graphs that can be embedded on any fixed two-dimensional

manifold In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a n ...

;. *graphs that are linklessly embeddable in Euclidean 3-space, and graphs that are knotlessly embeddable in Euclidean 3-space; *graphs with a feedback vertex set of size bounded by some fixed constant; graphs with Colin de Verdière graph invariant bounded by some fixed constant; graphs with

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

, pathwidth, or

branchwidth In graph theory, a branch-decomposition of an undirected graph ''G'' is a hierarchical clustering of the edges of ''G'', represented by an unrooted binary tree ''T'' with the edges of ''G'' as its leaves. Removing any edge from ''T'' partitions ...

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

loop Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...

graph (or, if one restricts to

simple graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

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.

states that a graph is planar if and only if it has neither ''K''₅ nor ''K''_3,3 as a minor. In other words, the set is an obstruction set for the set of all planar graphs, and in fact the unique minimal obstruction set. A similar theorem states that ''K''₄ and ''K''_2,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 graphs 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 it contains at least 17,535 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

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 mathematics, a cubic function is a function of the form f(x)=ax^3+bx^2+cx+d where the coefficients , , , and are complex numbers, and the variable takes real values, and a\neq 0. In other words, it is both a polynomial function of degree ...

in the size of the larger graph (although there is a constant factor in this polynomial that depends superpolynomially on the size of ''G''), which has been improved to quadratic time by Kawarabayashi, Kobayashi, and Reed. 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.; , Section 6. 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 invariant Graph may refer to: Mathematics * Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discr ...

s 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 In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

. 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 Independence is a condition of a person, nation, country, or state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independence is the stat ...

phenomenon by being ''unprovable'' in various formal systems that are much stronger than

Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearl ...

, yet being ''provable'' in systems much weaker than ZFC: :Theorem: For every positive integer ''n'', there is an integer ''m'' so large that if ''G''₁, ..., ''G''_''m'' is a sequence of finite undirected graphs, :where each ''G''_''i'' has size at most ''n''+''i'', then ''G''_''j'' ≤ ''G''_''k'' for some ''j'' < ''k''. (Here, the ''size'' of a graph is the total number of its vertices and edges, and ≤ denotes the minor ordering.)

Notes

References

*. *. *. *. *. *. *. *. *. *.

External links

* {{DEFAULTSORT:Robertson-Seymour theorem Graph minor theory Wellfoundedness Theorems in graph theory