Robertson–Seymour theorem

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, the Robertson–Seymour theorem (also called the graph minor theorem) states that the <a href="/facts/Undirected_graph/kw3eIBUe">undirected graphs</a>, <a href="/facts/Partial_order/qb4a3FAX">partially ordered</a> by the <a href="/facts/Minor_(graph_theory)/qn5eI22T">graph minor</a> relationship, form a <a href="/facts/Well-quasi-ordering/suQavGN9">well-quasi-ordering</a>. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of <a href="/facts/Forbidden_minor/50Kex6JU">forbidden minors</a>, in the same way that <a href="/facts/Wagner%27s_theorem/AHbRuRuu">Wagner's theorem</a> characterizes the <a href="/facts/Planar_graph/plREagr9">planar graphs</a> as being the graphs that do not have the <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> K5 or the <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> K3,3 as minors.
The Robertson–Seymour theorem is named after mathematicians <a href="/facts/Neil_Robertson_(mathematician)/nC5FXjur">Neil Robertson</a> and <a href="/facts/Paul_Seymour_(mathematician)/AJp2GgAC">Paul D. Seymour</a>, 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 <a href="/facts/Klaus_Wagner_(mathematician)/80VWpmJK">Klaus Wagner</a>, although Wagner said he never conjectured it.
A weaker result for <a href="/facts/Tree_(graph_theory)/TCWk4Joy">trees</a> is implied by <a href="/facts/Kruskal%27s_tree_theorem/3q0G4cbP">Kruskal's tree theorem</a>, which was conjectured in 1937 by <a href="/facts/Andrew_V%C3%A1zsonyi/x5IXPdVU">Andrew Vázsonyi</a> and proved in 1960 independently by <a href="/facts/Joseph_Kruskal/KzpLEAyF">Joseph Kruskal</a> and S. Tarkowski.

Robertson–Seymour theorem open-in-new

Robertson–Seymour theorem