Conjecture de Barnette

La conjecture de Barnette est un problème non résolu en théorie des graphes, concernant les cycles hamiltoniens dans les graphes. Elle affirme que tout graphe biparti polyédrique cubique possède un cycle hamiltonien. Elle porte le nom de David W. Barnette, professeur émérite à l'université de Californie à Davis. Un graphe planaire est dit polyédrique si et seulement s'il est 3-sommet-connexe, c'est-à-dire s'il est encore connexe après la suppression de deux quelconques de ses sommets. Un graphe est biparti si ses sommets peuvent être colorés avec deux couleurs de telle sorte que chaque arête a des extrémités de couleurs différentes. Un graphe est cubique (ou 3-régulier) si chaque sommet est l'extrémité d'exactement trois arêtes. Enfin, un graphe est hamiltonien s'il existe un cycle qui passe par chacun de ses sommets exactement une fois. La conjecture de Barnette affirme que : Tout graphe polyédrique bipartite cubique est hamiltonien. Par le , un graphe planaire représente les arêtes et les sommets d'un polyèdre convexe si et seulement s'il est polyédrique. Un polyèdre tridimensionnel représente un graphe cubique si et seulement si c'est un polyèdre simple ; de plus, un graphe planaire est biparti si et seulement si, dans un plongement planaire du graphe, les cycles des faces ont tous une longueur paire. Par conséquent, la conjecture de Barnette peut aussi être énoncée sous la forme équivalente : Si un polyèdre convexe simple en trois dimensions a un nombre pair d'arêtes sur chacune de ses faces, alors le graphe du polyèdre a un cycle hamiltonien. P. G. Tait a conjecturé en 1884 que tout graphe polyédrique cubique est hamiltonien ; cette conjecture est connue sous le nom de conjecture de Tait. Elle a été réfutée par W. T. Tutte en 1946 ; celui-ci a construit un contre-exemple avec 46 sommets ; d'autres chercheurs ont ensuite trouvé des contre-exemples plus petits. Cependant, aucun de ces contre-exemples connus n'est biparti.