Wagner's theorem

Remarks

Deleting vertices or edges and contracting edges keep a plane drawing plane, so every minor of a planar graph is planar. Since $K_5$ and $K_{3,3}$ are not planar, a planar graph has neither as a minor. For the converse, if $G$ is not planar, Kuratowski's theorem gives a subgraph that is a subdivision of $K_5$ or of $K_{3,3}$. Contracting the subdivided paths of this subgraph back to single edges gives $K_5$ or $K_{3,3}$ as a minor. For example, the Petersen graph is not planar: contracting its five spokes gives $K_5$. Klaus Wagner published the theorem in 1937.

Going deeper

For a student

Wagner's theorem is the minor version of Kuratowski's theorem. It shows that the class of planar graphs is closed under minors and is described by exactly two forbidden minors. The Robertson–Seymour theorem says that every minor-closed class of graphs has such a finite description.