Graph minor

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> H is called a minor of the graph G if H can be formed from G by deleting edges, <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> and by <a href="/facts/Edge_contraction/PRqKXEkj">contracting edges</a>.
The theory of graph minors began with <a href="/facts/Wagner%2527s_theorem/AHbRuRuu">Wagner's theorem</a> that a graph is <a href="/facts/Planar_graph/plREagr9">planar</a> if and only if its minors include neither the <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> K5 nor the <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> K3,3. The <a href="/facts/Robertson%25E2%2580%2593Seymour_theorem/J7g4CJ74">Robertson–Seymour theorem</a> implies that an analogous <a href="/facts/Forbidden_minors/50Kex6JU">forbidden minor characterization</a> exists for every property of graphs that is preserved by deletions and edge contractions.
For every fixed graph H, it is possible to test whether H is a minor of an input graph G in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.
Other results and conjectures involving graph minors include the <a href="/facts/Graph_structure_theorem/tN6y8cAY">graph structure theorem</a>, according to which the graphs that do not have H as a minor may be formed by gluing together simpler pieces, and <a href="/facts/Hadwiger_conjecture_(graph_theory)/9m1YSAKy">Hadwiger's conjecture</a> relating the inability to <a href="/facts/Graph_coloring/J6HoBfP0">color a graph</a> to the existence of a large <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> as a minor of it. Important variants of graph minors include the topological minors and immersion minors.

Graph minor open-in-new

Graph minor