Wagner's theorem

K₅ (left) and K_3,3 (right) as minors of the nonplanar Petersen graph (shown as the small colored circles and solid black edges). The minors may be formed by deleting the red vertex and contracting edges that lie within a single yellow circle in the figure.

A clique-sum of two planar graphs and the Wagner graph, forming a K₅-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 K₅ (the complete graph on five vertices) nor K_3,3 (the utility graph, a complete bipartite graph on six vertices). Another result also sometimes known as Wagner's theorem states that a four-connected graph is planar if and only if it has no K₅ minor. That is, by assuming a higher level of connectivity, the other graph K_3,3 can be made unnecessary in the characterization. Using this fact, it is possible to decompose the graphs that do not have a K₅ minor into combinations of planar graphs and the eight-vertex Wagner graph, glued together by clique-sum operations.

Wagner published both theorems in 1937,^[1] subsequent to the 1930 publication of Kuratowski's theorem,^[2] 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 K₅ and K_3,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 K₅ and K_3,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.^[3]

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 (a generalization of Wagner's clique-sum decomposition of K₅-minor-free graphs)^[4] and the Robertson–Seymour theorem (a generalization of the forbidden minor characterization of planar graphs, stating that every graph family closed under the operation of taking minors has a characterization by a finite number of forbidden minors).^[5] Analogues of Wagner's theorem can also be extended to the theory of matroids: in particular, the same two graphs K₅ and K_3,3 (along with three other forbidden configurations) appear in a characterization of the graphic matroids by forbidden matroid minors.^[6]

References