Wagner's theorem

K5 (left) and K3,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 K5-free graph.

In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). 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.