Satz von Wagner

Der Satz von Wagner, , ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher im Jahre 1937 von dem Mathematiker Klaus Wagner veröffentlicht wurde. Der Satz ist verwandt mit dem Satz von Kuratowski und gibt wie dieser eine Charakterisierung plättbarer Graphen.

Formulierung des Satzes

Datei:Graph K5.svg

Abb. 1: Der Kuratowski-Graph <math>K_5</math>

Datei:Graph K3 3.svg

Abb. 2: Der Kuratowski-Graph <math>K_{3,3}</math>

Der Satz lautet wie folgt:<ref name="DJ-1">Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, S. 23–24</ref>

Ein endlicher schlichter Graph <math> G=(V,E)</math> ist plättbar genau dann, wenn in ihm kein Teilgraph enthalten ist, der zu einem der beiden Kuratowski-Graphen <math> K_5</math> und <math>K_{3,3}</math> kontrahierbar ist.

Anwendung

Mit dem Satz von Wagner lässt sich zeigen, dass der Petersen-Graph nicht plättbar ist.<ref name="DJ-2">Jungnickel, op. cit., S. 24</ref>

Folgerung

Die beiden Sätze von Kuratowski und Wagner führen zusammengenommen zu folgendem Resultat:<ref name="RD-1">Reinhard Diestel: Graph Theory. 2005, S. 96 ff., 101</ref>

Für einen endlichen schlichten Graphen <math>G=(V,E)</math> sind gleichwertig:

 <math> (I) </math>  : <math>G</math> ist plättbar.

 <math> (II) </math>  : In <math>G</math> ist keiner der beiden Kuratowski-Graphen als Minor enthalten.

 <math> (III) </math>  : In <math>G</math> ist keiner der beiden Kuratowski-Graphen als topologischer Minor enthalten.

Siehe auch

• Äquivalenzsatz von Wagner
• Satz von Wagner und Fáry
• Minorentheorem

Literatur

• Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. 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. Band 5). 3. Auflage. Springer Verlag, Berlin / Heidelberg / New York 2008, ISBN 978-3-540-72779-8 (MR2363884). 
• Klaus Wagner: Über eine Eigenschaft der ebenen Komplexe. In: Mathematische Annalen. Band 114, 1937, S. 570–590, doi:10.1007/BF01594196 (MR1513158). 
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4 (MR0282850). 

Einzelnachweise und Fußnoten

<references />