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]
- (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
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
- 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
