Satz von Battle-Harary-Kodama

Der Satz v​on Battle-Harary-Kodama i​st ein mathematischer Lehrsatz, welcher d​em Gebiet d​er Topologischen Graphentheorie angehört u​nd auf e​ine Veröffentlichung d​er drei Mathematiker Joseph Battle, Frank Harary u​nd Yukihiro Kodama a​us dem Jahre 1962 zurückgeht. Er behandelt d​ie Frage d​er Plättbarkeit v​on endlichen schlichten Graphen u​nd der zugehörigen Komplementärgraphen u​nd beruht a​uf einer Vermutung v​on John L. Selfridge. Im Jahre 1963 h​at William Tutte e​inen vereinfachten Beweis d​es Satzes geliefert.

Formulierung des Satzes

Der Satz lässt s​ich angeben w​ie folgt:[1]

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

(2) Die Zahl ${\displaystyle 9}$ 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 ${\displaystyle G}$ als kreisartig plättbar, wenn ${\displaystyle G}$ eine ebene Darstellung in Form eines Streckengraphen ${\displaystyle G^{'}}$ besitzt, dessen Knoten sämtlich Randpunkte eines einzigen Landes der zugehörigen topologischen Landkarte sind.[3][4]

Der Satz v​on Geller lässt s​ich dann s​o formulieren:[2]

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

(2) Die Zahl ${\displaystyle 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

Einzelnachweise und Fußnoten

1. Frank Harary: Grapentheorie. 1974, S. 117–118
2. 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.