A planar embedding of a given graph is a drawing of the graph in the Euclidean plane, with points for its vertices and curves for its edges, in such a way that the only intersections between pairs of edges are at a common endpoint of the two edges. A minor of a given graph is another graph formed by deleting vertices, deleting edges, and contracting edges. When an edge is contracted, its two endpoints are merged to form a single vertex. 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. Wagner's theorem states that every graph has either a planar embedding, or a minor of one of two types, the complete graphK5 or the complete bipartite graphK3,3. If a given graph is planar, so are all its minors: vertex and edge deletion obviously preserve planarity, and edge contraction can also be done in a planarity-preserving way, by leaving one of the two endpoints of the contracted edge in place and routing all of the edges that were incident to the other endpoint along the path of the contracted edge. A minor-minimal non-planar graph is a graph that is not planar, but in which all proper minors are planar. Another way of stating Wagner's theorem is that there are only two minor-minimal non-planar graphs, K5 and K3,3. Another result also sometimes known as Wagner's theorem states that a four-connected graph is planar if and only if it has no K5minor. 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. Correspondingly, the Kelmans–Seymour conjecture states that a 5-connected graph is planar if and only if it does not have K5 as a topological minor.
Wagner published both theorems in 1937, subsequent to the 1930 publication of Kuratowski's theorem, according to which a graph is planar if and only if it does not contain as a subgraph a subdivision of one of the same two forbidden graphs K5 and K3,3. In a sense, Kuratowski's theorem is stronger than Wagner's theorem: a subdivision can be converted into a minor of the same type by contracting all but one edge in each path formed by the subdivision process, but converting a minor into a subdivision of the same type is not always possible. However, in the case of the two graphs K5 and K3,3, it is straightforward to prove that a graph that has at least one of these two graphs as a minor also has at least one of them as a subdivision, so the two theorems are equivalent.
Implications
One consequence of the stronger version of Wagner's theorem for four-connected graphs is to characterize the graphs that do not have a K5 minor. The theorem can be rephrased as stating that every such graph is either planar or it can be decomposed into simpler pieces. Using this idea, the K5-minor-free graphs may be characterized as the graphs that can be formed as combinations of planar graphs and the eight-vertex Wagner graph, glued together by clique-sumoperations. For instance, K3,3 can be formed in this way as a clique-sum of three planar graphs, each of which is a copy of the tetrahedral graphK4. Wagner's theorem is an important precursor to the theory of graph minors, which culminated in the proofs of two deep and far-reaching results: the graph structure theorem and the Robertson–Seymour theorem. Analogues of Wagner's theorem can also be extended to the theory of matroids: in particular, the same two graphs K5 and K3,3 appear in a characterization of the graphic matroids by forbidden matroid minors.
