A graph H is a minor of a graph G if a copy of H can be obtained from G via repeated edge deletion and/or edge contraction. The Kuratowski reduction theorem states that any nonplanar graph has the complete graph K_5 or the complete bipartite graph K_(3, 3) as a minor. In addition, any snark has the Petersen graph as a minor, as conjectured by Tutte (1967; West 2000, p. 304) and proved by Robertson et al. The determination of graph minors is an NP-hard problem for which no good algorithms are known, although brute-force methods such as those due to Robertson, Sanders, and Thomas exist.

edge contraction | forbidden minor | Kuratowski's theorem | projective plane crossing number | Robertson-Seymour theorem | topological minor