Wagner's theorem
In
Definitions and statement
A planar
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 (minors formed by at least one deletion or contraction) 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
History and relation to Kuratowski's theorem
Wagner published both theorems in 1937,
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-sum operations. 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 graph K4.
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 K5-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 K5 and K3,3 (along with three other forbidden configurations) appear in a characterization of the graphic matroids by forbidden matroid minors.[6]
References
- S2CID 123534907.
- .
- ISBN 9781846289699.
- MR 2188176.
- ISBN 9781439826270.
- MR 0597159.