Der Satz von Battle-Harary-Kodama ist ein mathematischer Lehrsatz, welcher dem Gebiet der Topologischen Graphentheorie angehört und auf eine Veröffentlichung der drei Mathematiker Joseph Battle, Frank Harary und Yukihiro Kodama aus dem Jahre 1962 zurückgeht. Er behandelt die Frage der Plättbarkeit von endlichen schlichten Graphen und der zugehörigen Komplementärgraphen und beruht auf einer Vermutung von John L. Selfridge. Im Jahre 1963 hat William Tutte einen vereinfachten Beweis des Satzes geliefert.

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:[1]

(1) Ist ein endlicher schlichter Graph   plättbar und hat er   Knoten, so ist sein Komplementärgraph   nicht plättbar.
(2) Die Zahl   ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Verwandter Satz

Bearbeiten

Von Dennis P. Geller wurde ein verwandter Satz vorgelegt,[2] welcher die analoge Frage in Bezug auf die Eigenschaft der kreisartigen Plättkeit behandelt. Hier bezeichnet man einen endlichen schlichten Graphen   als kreisartig plättbar, wenn   eine ebene Darstellung in Form eines Streckengraphen   besitzt, dessen Knoten sämtlich Randpunkte eines einzigen Landes der zugehörigen topologischen Landkarte sind.[3][4]

Der Satz von Geller lässt sich dann so formulieren:[2]

(1) Ist ein endlicher schlichter Graph   kreisartig plättbar und hat er   Knoten, so ist sein Komplementärgraph   nicht kreisartig plättbar.
(2) Die Zahl   ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Quellen und Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten
  1. Frank Harary: Grapentheorie. 1974, S. 117–118
  2. a b Harary, op. cit., S. 118
  3. Harary, op. cit., S. 116
  4. In diese Begriffsfassung geht entscheidend der Satz von Wagner und Fáry ein.