Wagner theorem

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 ${\displaystyle K_{5}}$

Fig. 2: The Kuratowski graph ${\displaystyle K_{3,3}}$

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 . ${\displaystyle G=(V,E)}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

application

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

Inference

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

For a finite simple graph, the following are equivalent: ${\displaystyle G=(V,E)}$

  ${\displaystyle (I)}$  : is flattenable. ${\displaystyle G}$

  ${\displaystyle (II)}$  : In neither of the two Kuratowski graphs is contained as a minor . ${\displaystyle G}$

  ${\displaystyle (III)}$  : In neither of the two Kuratowski graphs is included as a topological minor . ${\displaystyle G}$

See also

• Wagner equivalence theorem
• Theorem by Wagner and Fáry
• Minor theorem

literature

• Reinhard Diestel : Graph Theory (=  Graduate Texts in Mathematics . Volume 173 ). 3. Edition. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6 ( MR2159259 ).
• Dieter Jungnickel : Graphs, Networks and Algorithms . With 209 Figures and 9 Tables (=  Algorithms and Computation in Mathematics . Volume 5 ). 3. Edition. Springer Verlag, Berlin / Heidelberg / New York 2008, ISBN 978-3-540-72779-8 ( MR2363884 ).
• Klaus Wagner: About a property of the flat complexes . In: Mathematical Annals . tape 114 , 1937, pp. 570-590 , doi : 10.1007 / BF01594196 ( MR1513158 ).
• Klaus Wagner: Theory of graphs (=  BI university pocket books. 248 / 248a). Bibliographisches Institut, Mannheim ( inter alia ) 1970, ISBN 3-411-00248-4 ( MR0282850 ).

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