Set of Battle Harary Kodama

The Battle-Harary-Kodama theorem is a mathematical theorem which belongs to the field of topological graph theory and goes back to a publication by the three mathematicians Joseph Battle , Frank Harary and Yukihiro Kodama in 1962. It deals with the question of the smoothability of finite, simple graphs and the associated complementary graphs and is based on a conjecture by John L. Selfridge . In 1963 William Tutte gave a simplified proof of the theorem.

Formulation of the sentence

The sentence can be stated as follows:

(1) If a finite, simple graph is flattenable and if it has nodes , then its complementary graph is not flattenable. ${\ displaystyle G = (V, E)}$ ${\ displaystyle p \ geq 9}$ ${\ displaystyle {\ overline {G}} = (V, {\ binom {V} {2}} \ setminus E)}$

(2) The number is the smallest natural number with this property. ${\ displaystyle 9}$

Related sentence

A related sentence was put forward by Dennis P. Geller , which deals with the analogous question regarding the property of circular flatness . A finite, simple graph is referred to as circularly flattenable if it has a planar representation in the form of a line graph , the nodes of which are all edge points of a single country on the associated topological map . ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle G ^ {'}}$

Geller's theorem can then be formulated as follows:

(1) If a finite, simple graph can be flattened in a circle and if it has nodes, then its complementary graph cannot be flattened in a circle. ${\ displaystyle G}$ ${\ displaystyle p \ geq 7}$ ${\ displaystyle {\ overline {G}}}$

(2) The number is the smallest natural number with this property. ${\ displaystyle 7}$

Sources and literature

Joseph Battle, Frank Harary, Yukihiro Kodama: Every planar graph with nine points has a nonplanar complement . In: Bull. Amer. Math. Soc. (NS) . tape 68 , 1962, pp. 569-571 ( projecteuclid.org ). MR0155314
Frank Harary: Graph Theory . R. Oldenbourg Verlag , Munich, Vienna 1974, ISBN 3-486-34191-X .
WT Tutte: The non-biplanar character of the complete 9-graph . In: Canadian Mathematical Bulletin . tape 6 , 1963, pp. 319-319 ( math.ca ). MR0159318

References and footnotes

^ Frank Harary: Grape theory. 1974, pp. 117-118
↑ ^a ^b Harary, op.cit., P. 118
↑ Harary, op.cit., P. 116
↑ The theorem of Wagner and Fáry plays a decisive role in this definition .

[FH-1] Frank Harary: Grape theory. 1974, pp. 117-118

[FH-2-2] Harary, op.cit., P. 118

[FH-3-3] Harary, op.cit., P. 116

[4] The theorem of Wagner and Fáry plays a decisive role in this definition .