Wagner theorem

from Wikipedia, the free encyclopedia

The set of Wagner , english Wagner's theorem is a proposition from the mathematical branch of topological graph theory , which in 1937 by the mathematician Klaus Wagner published was. The theorem is related to Kuratowski's theorem and, like the latter, gives a characterization of flattenable graphs .

Formulation of the sentence

Fig. 1: The Kuratowski graph
Fig. 2: The Kuratowski graph

The sentence is as follows:

A finite, simple graph can be flattened if and only if it does not contain a subgraph that is contractible to one of the two Kuratowski graphs and .


With Wagner's theorem it can be shown that the Petersen graph cannot be flattened.


The two sentences by Kuratowski and Wagner together lead to the following result:

For a finite simple graph, the following are equivalent:
   : is flattenable.
   : In neither of the two Kuratowski graphs is contained as a minor .
   : In neither of the two Kuratowski graphs is included as a topological minor .

See also


References and footnotes

  1. ^ Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, pp. 23-24
  2. Jungnickel, op.cit., P. 24
  3. ^ Reinhard Diestel: Graph Theory. 2005, p. 96 ff., 101