title: 54-graphe de Ellingham-Horton
text: # 54-graphe de Ellingham-Horton
  
  Le 54-graphe de Ellingham-Horton est, en théorie des graphes, un graphe 3-régulier possédant 54 sommets et 81 arêtes. Il est construit comme contre-exemple à une conjecture de Tutte.
  
  ## Histoire
  
  En 1971, le mathématicien et cryptanalyste William Tutte conjecture qu'il n'existe pas de graphe 3-sommet-connexe qui soit cubique, biparti et non-hamiltonien. Mais J. D. Horton trouve un contre-exemple à 96 sommets, le graphe de Horton, publié par Bondy & Murty en 1976.
  
  Après cela, d'autres contre-exemples sont découverts. En 1982, c'est un graphe à 92 sommets, encore construit par Horton (le 92-graphe de Horton), puis, en 1983, Owens trouve un contre-exemple d'ordre 78.
  
  Avec Ellingham, Horton publie deux contre-exemples à la conjecture de Tutte : un graphe d'ordre 78 en 1981 (le 78-graphe de Ellingham-Horton) et un graphe d'ordre 54 en 1983 (le 54-graphe de Ellingham-Horton). À l'heure actuelle, ce graphe à 54 sommets est le plus petit graphe non-hamiltonien biparti cubique 3-sommet-connexe connu.
  
  ## Propriétés
  
  ### Propriétés générales
  
  Le diamètre du 54-graphe de Ellingham-Horton, l'excentricité maximale de ses sommets, est 10, son rayon, l'excentricité minimale de ses sommets, est 9 et sa maille, la longueur de son plus court cycle, est 6. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.
  
  ### Coloration
  
  Le nombre chromatique du 54-graphe de Ellingham-Horton est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.
  
  L'indice chromatique du 54-graphe de Ellingham-Horton est 3. Il existe donc une 3-coloration des arêtes du graphe telles que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
  
  