Graphe polyédrique

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 théorème de Balinski (en) 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 théorème de Steinitz (en), 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[1] - [2].

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[3]. Il existe également un graphe polyédrique non hamiltonien à 11 sommets dont toutes les faces sont des triangles, le graphe de Goldner-Harary[4].

Un résultat plus fort est qu'il existe une constante ${\displaystyle \alpha }$ strictement inférieure à ${\displaystyle 1}$, l'exposant de réduction (shortness exponent en anglais), ainsi qu'une famille infinie de graphes polyédriques tels que la longueur de la plus longue chaîne simple d'un graphe à ${\displaystyle n}$ sommets de la famille est d'ordre ${\displaystyle O(n^{\alpha })}$[5] - [6].

Duijvestijn a donné un décompte des graphes polyédriques jusqu'à 26 arêtes[7]. Le nombre de ces graphes avec 6, 7, 8, … arêtes est :

1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, …

C'est la suite A002840 de l'OEIS.

On peut aussi énumérer (en) les graphes polyédriques en fonction de leur nombre de sommets. Le nombre de ces graphes avec 4, 5, 6, … sommets est

1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, …

C'est la suite A000944 de l'OEIS.

Un graphe polyédrique est le graphe d'un polyèdre simple (en) s'il est cubique (si chaque sommet est de degré 3). C'est le graphe d'un polyèdre simplicial (en) si c'est un graphe maximal planaire (en).

Les graphes de Halin, des graphes formés à partir d'un arbre représenté dans un plan où l'on a relié toutes les feuilles de l'arbre, forment une autre famille importante de graphes polyédriques.

(en) Eric W. Weisstein, « Polyhedral Graph », sur MathWorld