Loading AI tools
De Wikipédia, l'encyclopédie libre
En mathématiques, et plus particulièrement en théorie des graphes, la conjecture de Tait affirme que « tout graphe cubique planaire 3-connexe possède un cycle hamiltonien ».
Elle a été formulée par P. G. Tait (en 1884)[1] et réfutée par W. T. Tutte (en 1946)[2] : il a construit un contre-exemple avec 25 faces, 69 arêtes et 46 sommets. Plusieurs autres contre-exemples plus petits, avec 21 faces, 57 arêtes et 38 sommets, ont été donnés plus tard, notamment le graphe de Barnette-Bosák-Lederberg, et étudiés par Holton et McKay (en 1988)[3] qui ont démontré qu’ils sont de taille minimale. La condition sur le graphe d’être 3-régulier est nécessaire : il existe des polyèdres tels que le dodécaèdre rhombique, qui est un graphe biparti avec six sommets de degré quatre d'un côté et huit sommets de degré trois de l'autre; pour ce graphe, un cycle hamiltonien doit alterner entre les deux côtés de la bipartition, mais comme les deux parties n'ont pas le même nombre de sommets, le dodécaèdre rhombique n'est pas hamiltonien.
La conjecture avait historiquement une certaine importance car, si elle avait été vraie, elle aurait impliqué le théorème des quatre couleurs : comme Tait l'a décrit, le problème des quatre couleurs est équivalent au problème de trouver une coloration des arêtes d'un graphe planaire cubique sans pont avec trois couleurs. Dans un graphe planaire cubique hamiltonien, une telle coloration des arêtes est facile à construire : on utilise deux couleurs alternativement sur le cycle et une troisième couleur pour toutes les arêtes restantes. On peut aussi construire une 4-coloration des faces d'un graphe planaire cubique hamiltonien directement, en utilisant deux couleurs pour les faces à l'intérieur du cycle et deux autres couleurs pour les faces à l'extérieur.
La notion centrale de ce contre-exemple est un graphe que l'on appelle maintenant le fragment de Tutte, illustré ci-contre.
Si ce fragment fait partie d'un graphe plus grand, alors tout cycle hamiltonien du graphe doit entrer ou sortir par le sommet du haut (et entrer ou sortir par l'un des deux sommets du bas). Il ne peut pas entrer par l’un sommet du bas et sortir par l'autre.
Les fragments de Tutte sont utilisés pour construire le graphe de Tutte qui est non hamiltonien, en assemblant trois de ces fragments comme indiqué sur la figure. Les arêtes « obligatoires » des fragments, c’est-à-dire celles qui doivent faire partie de tout chemin hamiltonien traversant les fragments, sont connectés au sommet central ; comme tout cycle ne peut utiliser que deux de ces trois arêtes, il ne peut y avoir de cycle hamiltonien.
Le graphe de Tutte résultant est 3-connexe et planaire et, par le théorème de Steinitz (de), c'est le graphe d'un polyèdre. Il a 25 faces, 69 arêtes et 46 sommets. Il peut être réalisé géométriquement à partir d'un tétraèdre dont les faces correspondent aux quatre grandes faces du dessin (trois entre des paires de fragments et la quatrième la face extérieure) en tronquant par multiplication trois de ses sommets.
Le graphe de Barnette-Bosák-Lederberg a 21 faces, 57 arêtes et 38 sommets. Holton & McKay (1988)[3] ont montré qu'il existe exactement six polyèdres non hamiltoniens à 38 sommets qui ont des coupes à trois arêtes non triviales. Ils sont formés en remplaçant deux des sommets d'un prisme pentagonal par le même fragment utilisé dans l'exemple de Tutte.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
