Editing Graph minor (section)

{{bots|deny=Citation bot}}
{{Short description|Subgraph with contracted edges}}

In [[graph theory]], an [[undirected graph]] {{mvar|H}} is called a '''minor''' of the graph {{mvar|G}} if {{mvar|H}} can be formed from {{mvar|G}} by deleting edges, [[Vertex (graph theory)|vertices]] and by [[edge contraction|contracting edges]].

The theory of graph minors began with [[Wagner's theorem]] that a graph is [[planar graph|planar]] if and only if its minors include neither the [[complete graph]] {{math|''K''<sub>5</sub>}} nor the [[complete bipartite graph]] {{math|''K''<sub>3,3</sub>}}.<ref name="w">{{harvtxt|Lovász|2006}}, p.&nbsp;77; {{harvtxt|Wagner|1937a}}.</ref> The [[Robertson–Seymour theorem]] implies that an analogous [[forbidden minors|forbidden minor characterization]] exists for every property of graphs that is preserved by deletions and edge contractions.<ref name="rst">{{harvtxt|Lovász|2006}}, theorem 4, p.&nbsp;78; {{harvtxt|Robertson|Seymour|2004}}.</ref>
For every fixed graph {{mvar|H}}, it is possible to test whether {{mvar|H}} is a minor of an input graph {{mvar|G}} in [[polynomial time]];<ref name="rs95"/> together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.<ref name="fl88"/>

Other results and conjectures involving graph minors include the [[graph structure theorem]], according to which the graphs that do not have {{mvar|H}} as a minor may be formed by gluing together simpler pieces, and [[Hadwiger conjecture (graph theory)|Hadwiger's conjecture]] relating the inability to [[graph coloring|color a graph]] to the existence of a large [[complete graph]] as a minor of it. Important variants of graph minors include the topological minors and immersion minors.