title: Théorème de Battle-Harary-Kodama
text: # 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. 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.
  
  ## Énoncé
  
  L'énoncé est le suivant :
  
  Théorème — Si un graphe simple planaire $G=(V,E)$ a au moins 9 sommets, alors son graphe complémentaire ${\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, 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. Le théorème de Geller s'énonce comme suit :
  
  Théorème — Si un graphe simple $G$ est planaire extérieur et a au moins 7 sommets, alors son graphe complémentaire ${\overline {G}}$ n'est pas planaire extérieur; de plus, le nombre 7 est le plus petit entier naturel avec cette propriété.
  
  