Klaus Wagner was a German

Germans

The Germans are a Germanic ethnic group native to Central Europe. The English term Germans has referred to the German-speaking population of the Holy Roman Empire since the Late Middle Ages....

 mathematician

Mathematician

A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....

. He studied topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

 at the University of Cologne

University of Cologne

The University of Cologne is one of the oldest universities in Europe and, with over 44,000 students, one of the largest universities in Germany. The university is part of the Deutsche Forschungsgemeinschaft, an association of Germany's leading research universities...

 under the supervision of Karl Dörge, who had been a student of Issai Schur

Issai Schur

Issai Schur was a mathematician who worked in Germany for most of his life. He studied at Berlin...

. Wagner received his Ph.D. in 1937, and taught at Cologne for many years himself. In 1970, he moved to the University of Duisburg

University of Duisburg

-History:Its origins date back to the 1555 decision to create a university for the unified duchies at the Lower Rhine that were later to be merged into Prussia. After the foundation of an academic college in 1559, a university was founded in 1655 by Frederick William, Elector of Brandenburg, the...

, where he remained until his retirement in 1978.

Wagner was honored in 1990 by a festschrift

Festschrift

In academia, a Festschrift , is a book honoring a respected person, especially an academic, and presented during his or her lifetime. The term, borrowed from German, could be translated as celebration publication or celebratory writing...

 on graph theory, and in June 2000, following Wagner's death, the University of Cologne hosted a Festkolloquium in his memory.

Graph minors

Wagner is known for his contributions to graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

 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 graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

s as exactly those graphs that do not have as a minor either a complete graph

Complete graph

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

 K₅ on five vertices or a complete bipartite graph

Complete bipartite graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...

 K_3,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

Homeomorphism (graph theory)

In graph theory, two graphs G and G' are homeomorphic if there is an isomorphism from some subdivision of G to some subdivision of G'...

 of K₅ or K_3,3.

Another result of his, also known as Wagner's theorem, is that a four-connected graph

K-vertex-connected graph

In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...

 is planar if and only if it has no K₅ minor. This implies a characterization of the graphs with no K₅ minor as being constructed from planar graphs and Wagner graph

Wagner graph

In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.-Properties:...

 (an eight-vertex Möbius ladder

Möbius ladder

In graph theory, the Möbius ladder Mn is a cubic circulant graph with an even number n of vertices, formed from an n-cycle by adding edges connecting opposite pairs of vertices in the cycle...

) by clique-sum

Clique-sum

In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology...

s, operations that glue together subgraphs at clique

Clique

A clique is an exclusive group of people who share common interests, views, purposes, patterns of behavior, or ethnicity. A clique as a reference group can be either normative or comparative. Membership in a clique is typically exclusive, and qualifications for membership may be social or...

s 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

Hadwiger conjecture (graph theory)

In graph theory, the Hadwiger conjecture states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph...

 on the chromatic number of K_k-minor-free graphs is equivalent to the four color theorem

Four color theorem

In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color...

. More complicated decompositions of graphs into clique-sums of simpler types of graphs, generalizing this result, have since become standard in graph minor theory.

Wagner conjectured in the 1930s (although this conjecture was not published until later) that in any infinite set of graphs, one graph is isomorphic to a minor of another. The truth of this conjecture implies that any family of graphs closed under the operation of taking minors (as planar graphs are) can automatically be characterized by finitely many forbidden minors analogously to Wagner's theorem characterizing the planar graphs. Neil Robertson

Neil Robertson (mathematician)

G. Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor at the Ohio State University. He earned his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. According to the criteria of the Erdős Number...

 and Paul Seymour finally published a proof of Wagner's conjecture in 2004 and it is now known as the Robertson–Seymour theorem

Robertson–Seymour theorem

In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...

.