Halin 圖,有時被稱為無頂多面體,是由具有四個或更多頂點、沒有度數為 2 的頂點,並且透過將樹的所有葉子與繞樹邊界傳遞的迴圈連線而構造的樹的平面嵌入構造的多面體圖。 Halin 圖的例子包括輪圖 、三角形稜柱圖
和 Frucht 圖。 上面說明了這些以及 Halin 圖的其他一些示例。
頂點數為 、2、... 的 Halin 圖的數量為 0、0、0、1、1、2、2、4、6、13、22、50、106、252、... (OEIS A346779) (E. Weisstein, 8 月 3 日 - 9 月 29 日,2021 年)。
具有 個頂點和
條邊的圖是 Halin 圖 當且僅當 它是多面體的(即,平面且 3-連通的),並且具有一個面,該面的頂點數等於圖的環秩
。
Halin 圖是哈密頓圖,並且在刪除任何單個頂點後仍然是哈密頓圖(Cornuéjols等人,1983 年)。 Halin 圖的樹寬為 3(Bodlaender,1988 年),是非二分圖,並且包含三角形(三階迴圈)。
第 個
節點 Halin 圖對於(至少)以下
值是火柴棍圖:(7, 1)(輪圖
)、(10, 3)、(10, 8)、(10, 10)、(11, 18)、(12, 6)、(12, 8)、(12, 10)、(12, 12)、(12, 16)、(12, 17)、(12, 21)、(12, 23)、(12, 30)、(12, 33)和(12, 34)。