Graph minor

Subgraph with contracted edges

In graph theory, an undirected graph H is called a minor of the undirected graph G if H can be formed from G by deleting edges and 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. 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.

From Wikipedia, under CC BY-SA. More on occurri.