Théorème de Battle-Harary-Kodama

Le théorème de Battle-Harary-Kodama est un théorème mathématique de la théorie topologique des graphes et qui doit son intitulé à une publication des mathématiciens Joseph Battle, Frank Harary et Yukihiro Kodama de l’année 1962[1]. Le théorème est une réponse à une question sur la planarité de certains graphes simples et de leur graphe complémentaire et résout une conjecture de John L. Selfridge. Une démonstration plus simple a été donnée un peu plus tard, en 1963, par William Tutte[2].

Énoncé

L'énoncé est le suivant[3] :

Théorème — Si un graphe simple planaire G = ( V , E ) {\displaystyle G=(V,E)} a au moins 9 sommets, alors son graphe complémentaire[4] G ¯ = ( V , E ¯ ) {\displaystyle {\overline {G}}=(V,{\overline {E}})} n'est pas planaire ; de plus, le nombre 9 est le plus petit entier naturel avec cette propriété.

Énoncé voisin

Un énoncé voisin, donné par Dennis P. Geller[5], traite la question de la « planarité extérieure » : un graphe est planaire extérieur s'il admet une représentation plane dans laquelle les sommets se trouvent tous sur le bord de la face extérieure[6]. Le théorème de Geller s'énonce comme suit :

Théorème — Si un graphe simple G {\displaystyle G} est planaire extérieur et a au moins 7 sommets, alors son graphe complémentaire G ¯ {\displaystyle {\overline {G}}} n'est pas planaire extérieur; de plus, le nombre 7 est le plus petit entier naturel avec cette propriété.

Bibliographie

  • Joseph Battle, Frank Harary et Yukihiro Kodama, « Every planar graph with nine points has a nonplanar complement », Bull. Amer. Math. Soc. (N.S.), vol. 68,‎ , p. 569–571 (MR 0155314, lire en ligne)
  • Frank Harary, Graph Theory, Addison-Wesley, (SUDOC 014230593)
  • William T. Tutte, « The non-biplanar character of the complete 9-graph », Canadian Mathematical Bulletin, vol. 6,‎ , p. 319–319 (lire en ligne)

Notes et références

  1. ↑ Battle, Harary et Kodama 1962.
  2. ↑ Tutte 1963.
  3. ↑ Harary 1969, Théorème 11.11.
  4. ↑ Le graphe complémentaire G ¯ = ( V , E ¯ ) {\displaystyle {\overline {G}}=(V,{\overline {E}})} a pour ensemble d'arêtes l'ensemble complémentaire E ¯ {\displaystyle {\overline {E}}} de l'ensemble E {\displaystyle E} des arêtes de G {\displaystyle G} .
  5. ↑ Harary 1969, Théorème 11.12.
  6. ↑ Harary 1969, p. 106.
  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique