Klaus Wagner (March 31, 1910 – February 6, 2000) was a
German
German(s) may refer to:
* Germany (of or related to)
** Germania (historical use)
* Germans, citizens of Germany, people of German ancestry, or native speakers of the German language
** For citizens of Germany, see also German nationality law
**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, structure, space, models, and change.
History
On ...
known for his contributions to
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
.
Education and career
Wagner studied
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
at the
University of Cologne
The University of Cologne (german: Universität zu Köln) is a university in Cologne, Germany. It was established in the year 1388 and is one of the most prestigious and research intensive universities in Germany. It was the sixth university to ...
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 University of Berlin. He obtained his doctorate in 1901, became lecturer in 1903 and, after a stay at th ...
. Wagner received his Ph.D. in 1937, with a dissertation concerning the
Jordan curve theorem
In topology, the Jordan curve theorem asserts that every '' Jordan curve'' (a plane simple closed curve) divides the plane into an " interior" region bounded by the curve and an " exterior" region containing all of the nearby and far away exteri ...
and
four color theorem, 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
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
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 and 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 minors include neither ''K''5 (the complete graph on fi ...
characterizes the
planar graphs 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 is ...
''K''
5 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 i ...
''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 subgraph that is a subdi ...
, which states that the planar graphs are exactly those graphs that do not contain as a subgraph a
subdivision of ''K''
5 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''
5 minor. This implies a characterization of the graphs with no ''K''
5 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 utili ...
) by
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. If two graphs ''G'' and ''H'' each contain cliques of equal size, th ...
s, operations that glue together subgraphs at
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
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
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.
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 (born 11 February 1982) is an Australian professional snooker player who is a former world champion and former world number one. The only Australian to have won a ranking event, he is also the only player from outside the United ...
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 minor 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 c ...
.
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
Topologists
Graph theorists