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.