In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3.[1] The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.[2] For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time;[3] together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.[4]
Other results and conjectures involving graph minors include the graph structure theorem, according to which the graphs that do not have H as a minor may be formed by gluing together simpler pieces, and Hadwiger's conjecture relating the inability to 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.
rs95 was invoked but never defined (see the help page).fl88 was invoked but never defined (see the help page).