Satz von Wagner

Charakterisierung plättbarer Graphen

Der Satz von Wagner, englisch Wagner’s theorem, 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 SatzesBearbeiten

 
Abb. 1: Der Kuratowski-Graph  
 
Abb. 2: Der Kuratowski-Graph  

Der Satz lautet wie folgt:[1]

Ein endlicher schlichter Graph   ist plättbar genau dann, wenn in ihm kein Teilgraph enthalten ist, der zu einem der beiden Kuratowski-Graphen   und   kontrahierbar ist.

AnwendungBearbeiten

Mit dem Satz von Wagner lässt sich zeigen, dass der Petersen-Graph nicht plättbar ist.[2]

FolgerungBearbeiten

Die beiden Sätze von Kuratowski und Wagner führen zusammengenommen zu folgendem Resultat:[3]

Für einen endlichen schlichten Graphen   sind gleichwertig:
    :   ist plättbar.
    : In   ist keiner der beiden Kuratowski-Graphen als Minor enthalten.
    : In   ist keiner der beiden Kuratowski-Graphen als topologischer Minor enthalten.

Siehe auchBearbeiten

LiteraturBearbeiten

Einzelnachweise und FußnotenBearbeiten

  1. Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, S. 23–24
  2. Jungnickel, op. cit., S. 24
  3. Reinhard Diestel: Graph Theory. 2005, S. 96 ff., 101