Graphe de Halin

thumb|Un graphe de Halin. En théorie des graphes, une branche des mathématiques, un graphe de Halin est un graphe planaire construit à partir d'un arbre en reliant toutes ses feuilles dans un cycle qui fait le tour de l'arbre de telle façon que l'arbre reste planaire. On exige de plus que l'arbre comporte au moins quatre sommets et ne comporte pas de sommets de degré 2. Les graphes de Halin graphs sont nommés d'après le mathématicien allemand Rudolf Halin qui les a étudiés en 1971, mais les graphes de Halin cubiques avaient déjà été étudiés plus d'un siècle auparavant par Thomas Kirkman. thumb|Le graphe des arêtes d'un prisme triangulaire vu comme un graphe de Halin. L'arbre central est en bleu et le cycle extérieur est en noir. Les graphes roue (les graphes des arêtes d'une pyramide) sont des graphes de Halin ; leur arbre est un graphe étoile. Le graphe des arêtes d'un prisme triangulaire est également un graphe de Halin (figure). Le graphe de Frucht, un des plus petits graphes cubiques sans automorphisme de graphe trivial, est aussi un graphe de Halin. Tout graphe de Halin est un graphe planaire au nombre minimal d'arêtes qui est 3-connexe. Le permet d'en déduire que c'est un graphe polyédrique. Tout graphe de Halin a un planaire unique, au choix près de l’espace extérieur, c'est-à-dire un unique plongement dans une 2-sphère. Tout graphe de Halin est hamiltonien, et chaque arête du graphe appartient à un cycle hamiltonien. De plus, un graphe de Halin reste hamiltonien lorsque l'on supprime n'importe quel sommet. Tout graphe de Halin est presque pancyclique, dans le sens où il comporte des cycles de toutes les longueurs de à (le nombre de sommets) sauf éventuellement une unique longueur paire. De plus, un graphe de Halin reste presque pancyclique si une seule arête est contractée. Enfin, un graphe de Halin sans sommets intérieurs de degré 3 est pancyclique. Tout graphe de Halin a une largeur arborescente inférieure ou égale à 3.