Wagner's theorem

This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

In some versions of graph minor theory the graph resulting from a contraction is simplified by removing self-loops and multiple adjacencies, while in other version multigraphs are allowed, but this variation makes no difference to Wagner's theorem.

Another result also sometimes known as Wagner's theorem states that a four-connected graph is planar if and only if it has no K5 minor.

That is, by assuming a higher level of connectivity, the graph K3,3 can be made unnecessary in the characterization, leaving only a single forbidden minor, K5.

The theorem can be rephrased as stating that every such graph is either planar or it can be decomposed into simpler pieces.

K 5 (left) and K 3,3 (right) as minors of the nonplanar Petersen graph (small colored circles and solid black edges). The minors may be formed by deleting the red vertex and contracting edges within each yellow circle.
A clique-sum of two planar graphs and the Wagner graph, forming a K 5 -free graph.
Proof without words that a hypercube graph is non-planar using Kuratowski's or Wagner's theorems and finding either K 5 (top) or K 3,3 (bottom) subgraphs