Graph minor

Summary

A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from $G$ by deleting vertices, deleting edges and contracting edges. The minor relation is a partial order on finite graphs up to isomorphism. Many natural classes, such as planar graphs and forests, are closed under taking minors. Wagner's theorem describes planar graphs by two forbidden minors, and the Robertson–Seymour theorem shows that every minor-closed class has a finite list of forbidden minors.