Graphe pancyclique

vignette| Cycles de longueurs 3,4,5 et 6 dans le graphe d'un octaèdre, montrant qu'il est pancyclique. En théorie des graphes, un graphe pancyclique est un graphe qui contient des cycles de toutes les longueurs de trois jusqu'au nombre de sommets du graphe. Les graphes pancycliques sont une généralisation des graphes hamiltoniens qui ont un cycle qui passe par tous les sommets. Un graphe à sommets est pancyclique si, pour tout entier avec , le graphe contient un cycle de longueur . Il est nœud-pancyclique ou sommet-pancyclique si, pour chaque sommet et tout avec , il contient un cycle de longueur qui passe par . De même, il est arête-pancyclique si, pour chaque arête et tout , il contient un cycle de longueur qui utilise . Un graphe biparti ne peut pas être pancyclique, car il ne contient aucun cycle de longueur impaire, mais il est dit bipancyclique s'il contient des cycles de toutes les longueurs paires de 4 à n. Le nombre de graphes pancycliques à sommets est 0, 0, 1, 2, 7, 43, 372, 6132, 176797, 9302828, ... (). Un graphe planaire extérieur maximal est par définition un graphe formé par un polygone simple du plan en triangulant son intérieur. Un graphe planaire extérieur maximal est pancyclique, comme on peut le montrer par induction. La face externe du graphe est un cycle de longueur n, et la suppression d'un triangle connecté au reste du graphe par une seule arête (une feuille de l'arbre qui forme le graphe dual de la triangulation) forme un graphe planaire extérieur maximal sur un sommet de moins, graphe qui par induction a des cycles de toutes les longueurs restantes. En choisissant convenablement le triangle à supprimer, le même argument montre en plus qu'un graphe planaire extérieur maximal est nœud-pancyclique. Il en est de même pour les graphes qui ont un sous-graphe couvrant planaire extérieur maximal, comme c'est le cas par exemple pour les graphes roue. Un graphe planaire maximal est un graphe planaire dans lequel toutes les faces, même la face extérieure, sont des triangles.