Satz von Battle-Harary-Kodama

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

Der Satz lässt sich angeben wie folgt:

(1) Ist ein endlicher schlichter Graph $G=(V,E)$ plättbar und hat er $p\geq 9$ Knoten, so ist sein Komplementärgraph ${\overline {G}}=(V,{\binom {V}{2}}\setminus E)$ nicht plättbar.

(2) Die Zahl $9$ ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Verwandter Satz

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

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

(1) Ist ein endlicher schlichter Graph $G$ kreisartig plättbar und hat er $p\geq 7$ Knoten, so ist sein Komplementärgraph ${\overline {G}}$ nicht kreisartig plättbar.

(2) Die Zahl $7$ ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Quellen und Literatur

• Joseph Battle, Frank Harary, Yukihiro Kodama: Every planar graph with nine points has a nonplanar complement. In: Bull. Amer. Math. Soc. (N.S.). Band 68, 1962, S. 569–571 (projecteuclid.org).  MR0155314
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• W. T. Tutte: The non-biplanar character of the complete 9-graph. In: Canadian Mathematical Bulletin. Band 6, 1963, S. 319–319 (math.ca).  MR0159318