Conjecture de Tait

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 ».

Graphe de Tutte

La conjecture

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.

Le contre-exemple de Tutte
Fragment de Tutte.

Fragments de Tutte

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.

Le contre-exemple

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.

Des contre-exemples plus petits
Graphe de Barnette-Bosák-Lederberg.

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.

Énoncés liés

Notes et références
  1. Tait (1884).
  2. Tutte (1946).
  3. Holton et McKay 1988.
  4. Barnette's conjecture, the Open Problem Garden, retrieved 2009-10-12.

Bibliographie
  • D. A. Holton et B. D. McKay, « The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices », Journal of Combinatorial Theory, série B, vol. 45, no 3,‎ , p. 305–319 (DOI 10.1016/0095-8956(88)90075-5).
  • P. G. Tait, « Listing's Topologie », Philosophical Magazine 5e série, vol. 17,‎ , p. 30–46. Réimprimé dans Scientific Papers, Vol. II, p. 85–98.
  • W. T. Tutte, « On Hamiltonian circuits », Journal of the London Mathematical Society, vol. 21, no 2,‎ , p. 98–101 (DOI 10.1112/jlms/s1-21.2.98, lire en ligne).

Liens externes
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.