Klaus Wagner

Klaus Wagner (March 31, 1910 – February 6, 2000) was a German mathematician known for his contributions to graph theory. Wagner studied topology at the University of Cologne under the supervision of Karl Dörge who had been a student of Issai Schur. Wagner received his Ph.D. in 1937, with a dissertation concerning the Jordan curve theorem and four color theorem, and taught at Cologne for many years himself. In 1970, he moved to the University of Duisburg, where he remained until his retirement in 1978. Wagner is known for his contributions to graph theory and particularly the theory of graph minors, graphs that can be formed from a larger graph by contracting and removing edges. Wagner's theorem characterizes the planar graphs as exactly those graphs that do not have as a minor either a complete graph K5 on five vertices or a complete bipartite graph K3,3 with three vertices on each side of its bipartition. That is, these two graphs are the only minor-minimal non-planar graphs. It is closely related to, but should be distinguished from, Kuratowski's theorem, which states that the planar graphs are exactly those graphs that do not contain as a subgraph a subdivision of K5 or K3,3. Another result of his, also known as Wagner's theorem, is that a four-connected graph is planar if and only if it has no K5 minor. This implies a characterization of the graphs with no K5 minor as being constructed from planar graphs and Wagner graph (an eight-vertex Möbius ladder) by clique-sums, operations that glue together subgraphs at cliques of up to three vertices and then possibly remove edges from those cliques. This characterization was used by Wagner to show that the case k = 5 of the Hadwiger conjecture on the chromatic number of Kk-minor-free graphs is equivalent to the four color theorem. Analogous characterizations of other families of graphs in terms of the summands of their clique-sum decompositions have since become standard in graph minor theory.