Klaus Wagner (March 31, 1910 – February 6, 2000) was a

German German(s) may refer to: * Germany, the country of the Germans and German things **Germania (Roman era) * Germans, citizens of Germany, people of German ancestry, or native speakers of the German language ** For citizenship in Germany, see also Ge ...

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

known for his contributions to

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

Education and career

Wagner studied

topology Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...

at the

University of Cologne The University of Cologne () is a university in Cologne, Germany. It was established in 1388. It closed in 1798 before being re-established in 1919. It is now one of the largest universities in Germany with around 45,187 students. The Universit ...

under the supervision of who had been a student of

Issai Schur Issai Schur (10 January 1875 – 10 January 1941) was a Russian mathematician who worked in Germany for most of his life. He studied at the Humboldt University of Berlin, University of Berlin. He obtained his doctorate in 1901, became lecturer i ...

. Wagner received his Ph.D. in 1937, with a dissertation concerning the

Jordan curve theorem In topology, the Jordan curve theorem (JCT), formulated by Camille Jordan in 1887, asserts that every ''Jordan curve'' (a plane simple closed curve) divides the plane into an "interior" region Boundary (topology), bounded by the curve (not to be ...

and

four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...

, and taught at Cologne for many years himself. In 1970, he moved to the

University of Duisburg The old University of Duisburg was a university in Duisburg, Germany. 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 foundati ...

, where he remained until his retirement in 1978.

Graph minors

Wagner is known for his contributions to

and particularly the theory of

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

s, graphs that can be formed from a larger graph by contracting and removing edges.

Wagner's theorem 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 graph minor, minors include neither ''K''5 (the complete g ...

characterizes the

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), 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 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. A complete digraph is a directed graph in which every pair of distinct vertices i ...

''K''₅ on five vertices or a

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..Electronic edition page 17. Graph theory ...

''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 In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a Glossary of graph theory#Su ...

, which states that the planar graphs are exactly those graphs that do not contain as a subgraph a

subdivision Subdivision may refer to: Arts and entertainment * Subdivision (metre), in music * ''Subdivision'' (film), 2009 * "Subdivision", an episode of ''Prison Break'' (season 2) * ''Subdivisions'' (EP), by Sinch, 2005 * "Subdivisions" (song), by Rush ...

of ''K''₅ or ''K''_3,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 ''K''₅ minor. This implies a characterization of the graphs with no ''K''₅ minor as being constructed from planar graphs and

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 As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, ...

(an eight-vertex

Möbius ladder In graph theory, the Möbius ladder , for even numbers , is formed from an by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph, so-named because (with the exception of (the util ...

) by

clique-sum In graph theory, a branch of mathematics, a clique sum (or clique-sum) is a way of combining two graphs by gluing them together at a clique (graph theory), clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' ...

s, operations that glue together subgraphs at

clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...

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 There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include: * Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...

on the chromatic number of ''K_k''-minor-free graphs is equivalent to the

. 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. Wagner conjectured in the 1930s (although this conjecture was not published until later) that in any infinite set of graphs, one graph is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

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 Alexander Robertson (born 11 February 1982) is an Australian professional snooker player, who is a former List of World Snooker Championship winners, world champion and former List of world number one snooker players, world number one. He ...

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

Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is ...

Recognition

Wagner was honored in 1990 by a

festschrift In academia, a ''Festschrift'' (; plural, ''Festschriften'' ) is a book honoring a respected person, especially an academic, and presented during their lifetime. It generally takes the form of an edited volume, containing contributions from the h ...

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

Selected publications

References

{{DEFAULTSORT:Wagner, Klaus 1910 births 2000 deaths 20th-century German mathematicians German topologists Graph theorists