Editing Graph minor (section)

== Major results and conjectures ==
It is straightforward to verify that the graph minor [[binary relation|relation]] forms a [[partial order]] on the isomorphism classes of finite undirected graphs: it is [[Transitive relation|transitive]] (a minor of a minor of {{mvar|G}} is a minor of {{mvar|G}} itself), and {{mvar|G}} and {{mvar|H}} can only be minors of each other if they are isomorphic because any nontrivial minor operation removes edges or vertices. A [[deep result]] by [[Neil Robertson (mathematician)|Neil Robertson]] and [[Paul Seymour (mathematician)|Paul Seymour]] states that this partial order is actually a [[well-quasi-ordering]]: if an [[infinity|infinite]] list {{math|(''G''{{sub|1}}, ''G''{{sub|2}}, …)}} of finite graphs is given, then there always exist two indices {{math|''i'' < ''j''}} such that {{mvar|G{{sub|i}}}} is a minor of {{mvar|G{{sub|j}}}}. Another equivalent way of stating this is that any set of graphs can have only a finite number of [[minimal element]]s under the minor ordering.<ref>{{harvtxt|Diestel|2005}}, Chapter 12: Minors, Trees, and WQO; {{harvtxt|Robertson|Seymour|2004}}.</ref> This result proved a conjecture formerly known as Wagner's conjecture, after [[Klaus Wagner]]; Wagner had conjectured it long earlier, but only published it in 1970.<ref>{{harvtxt|Lovász|2006}}, p.&nbsp;76.</ref>

In the course of their proof, Seymour and Robertson also prove the [[graph structure theorem]] in which they determine, for any fixed graph {{mvar|H}}, the rough structure of any graph that does not have {{mvar|H}} as a minor.  The statement of the theorem is itself long and involved, but in short it establishes that such a graph must have the structure of a [[clique-sum]] of smaller graphs that are modified in small ways from graphs [[graph embedding|embedded]] on surfaces of bounded [[Genus (mathematics)|genus]].
Thus, their theory establishes fundamental connections between graph minors and [[graph embedding|topological embeddings]] of graphs.<ref>{{harvtxt|Lovász|2006}}, pp. 80–82; {{harvtxt|Robertson|Seymour|2003}}.</ref>
 
For any graph {{mvar|H}}, the simple {{mvar|H}}-minor-free graphs must be [[sparse graph|sparse]], which means that the number of edges is less than some constant multiple of the number of vertices.<ref>{{harvtxt|Mader|1967}}.</ref> More specifically, if {{mvar|H}} has {{mvar|h}} vertices, then a simple {{mvar|n}}-vertex simple {{mvar|H}}-minor-free graph can have at most <math>\scriptstyle O(nh\sqrt{\log h})</math> edges, and some {{mvar|K{{sub|h}}}}-minor-free graphs have at least this many edges.<ref>{{harvtxt|Kostochka|1982}}; {{harvtxt|Kostochka|1984}}; {{harvtxt|Thomason|1984}}; {{harvtxt|Thomason|2001}}.</ref> Thus, if {{mvar|H}} has {{mvar|h}} vertices, then {{mvar|H}}-minor-free graphs have average [[degree (graph theory)|degree]] <math>\scriptstyle O(h \sqrt{\log h})</math> and furthermore [[Degeneracy (graph theory)|degeneracy]] <math>\scriptstyle O(h \sqrt{\log h})</math>. Additionally, the {{mvar|H}}-minor-free graphs have a separator theorem similar to the [[planar separator theorem]] for planar graphs: for any fixed {{mvar|H}}, and any {{mvar|n}}-vertex {{mvar|H}}-minor-free graph {{mvar|G}}, it is possible to find a subset of <math>\scriptstyle O(\sqrt{n})</math> vertices whose removal splits {{mvar|G}} into two (possibly disconnected) subgraphs with at most {{math|{{frac|2''n''|3}}}} vertices per subgraph.<ref>{{harvtxt|Alon|Seymour|Thomas|1990}}; {{harvtxt|Plotkin|Rao|Smith|1994}}; {{harvtxt|Reed|Wood|2009}}.</ref> Even stronger, for any fixed {{mvar|H}}, {{mvar|H}}-minor-free graphs have [[treewidth]] <math>\scriptstyle O(\sqrt{n})</math>.<ref>{{harvtxt|Grohe|2003}}</ref>

The [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]] in graph theory proposes that if a graph {{mvar|G}} does not contain a minor isomorphic to the [[complete graph]] on {{mvar|k}} vertices, then {{mvar|G}} has a [[graph coloring|proper coloring]] with {{math|''k'' – 1}} colors.<ref>{{harvtxt|Hadwiger|1943}}.</ref> The case {{math|1=''k'' = 5}} is a restatement of the [[four color theorem]]. The Hadwiger conjecture has been proven for {{math|''k'' ≤ 6}},<ref>{{harvtxt|Robertson|Seymour|Thomas|1993}}.</ref> but is unknown in the general case. {{harvtxt|Bollobás|Catlin|Erdős|1980}} call it "one of the deepest unsolved problems in graph theory." Another result relating the four-color theorem to graph minors is the [[snark theorem]] announced by Robertson, Sanders, Seymour, and Thomas, a strengthening of the four-color theorem conjectured by [[W. T. Tutte]] and stating that any [[Bridge (graph theory)|bridgeless]] [[cubic graph|3-regular graph]] that requires four colors in an [[edge coloring]] must have the [[Petersen graph]] as a minor.<ref>{{harvtxt|Thomas|1999}}; {{harvtxt|Pegg|2002}}.</ref>