Kelmans–Seymour conjecture states that a 5-connected graph is planar if and only if it does not have K5 as a topological minor. History and relation to Kuratowski's theorem 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-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) 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). 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. References Planar graphs Graph minor theory Theorems in graph theory