Graphe polyédrique

En théorie des graphes, une branche des mathématiques, un graphe polyédrique est un graphe non orienté défini en termes géométriques : il représente les sommets et les arêtes d'un polyèdre convexe. On peut aussi définir un graphe polyédrique en termes purement issus de la théorie des graphes : c'est un graphe planaire 3 sommet-connexe. Le diagramme de Schlegel d'un polyèdre convexe représente ses sommets et ses arêtes par des points et des segments de droite dans le plan euclidien. La figure résultante est un polygone convexe subdivisé en polygones plus petits. On peut associer à cette figure un graphe. Cette figure n'a pas de croisements, de telle sorte qu'un graphe polyédrique est un graphe planaire. De plus, le affirme que c'est un graphe 3 sommet-connexe, c'est-à-dire qu'il faut en retirer trois sommets avant qu'ils ne soient plus connexes. En sens inverse, d'après le , un graphe planaire 3 sommet-connexe caractérise complètement un polyèdre. Plus précisément, quand un graphe est à la fois planaire et 3-connexe, il existe un polyèdre dont les sommets et les arêtes forment un graphe isomorphe au graphe de départ. thumb|Le graphe de Herschel, polyédrique mais non hamiltonien. On peut se rendre compte qu'il est planaire en déplaçant le sommet central à l'extérieur. Selon la conjecture de Tait, tout graphe polyédrique cubique (c'est-à-dire tout graphe polyédrique où chaque sommet voit arriver exactement trois arêtes) posséderait un cycle hamiltonien. Cette conjecture a été infirmée par un contre-exemple de William Tutte, le graphe de Tutte, qui est polyédrique et cubique, mais pas hamiltonien. Si l'on ne demande plus au graphe d'être cubique, il y a des graphes polyédriques non hamiltoniens bien plus petits. Celui avec le moins de sommets et d'arêtes est le graphe de Herschel à 11 sommets et à 18 arêtes. Il existe également un graphe polyédrique non hamiltonien à 11 sommets dont toutes les faces sont des triangles, le graphe de Goldner-Harary.