火柴圖

火柴圖是一個簡單圖，它具有一個圖嵌入，該嵌入是平面的，其中所有頂點之間的距離都是單位距離，並且是非退化的（因此沒有頂點重合，沒有邊交叉或重疊，也沒有頂點與其不關聯的邊重合）。

在 條邊上找到拓撲上不同的火柴圖的數量的問題被稱為火柴問題（Gardner 1991，第 79-81 頁）。

在 , 2, ... 個節點上的連通火柴圖的數量是 1, 1, 2, 5, 13, 50, ... (OEIS A303792; E. Weisstein, 2018 年 4 月 30 日)，其中前幾個如上圖所示。連通的 6-火柴圖比 個頂點的連通單位距離圖少一個，即 ，如下文進一步討論，它既有平面嵌入又有單位距離嵌入，但沒有一個同時具有這兩種屬性的單一嵌入。

在 , 2, ... 條邊上的連通火柴圖的數量是 1, 1, 3, 5, 12, 28, 74, 207, 633, 2008, ... (OEIS A066951; Salvia 2015, Vaisse)，其中前幾個如上圖所示。

測試一個圖是否是火柴圖是 NP-困難的 (Eades and Wormland 1990, Cabello et al. 2007, Salvia 2015)。

以下是屬於火柴圖的圖的類別

1. 主教圖、黑主教圖和白主教圖，

2. 非重疊的支撐多邊形，

3. 環圖 ,

4. 空圖 (顯然地)，

5. 齒輪圖，

6. Jahangir 圖 ，其中 ,

7. 梯形圖 ,

8. 梯子橫檔圖 ,

9. 鍋圖，

10. 路徑圖 ,

11. 多六邊形，

12. 多鑽石形，

13. 多米諾骨牌，

14. Sierpiński 地毯圖，

15. Sierpiński 墊片圖，

16. 星圖 ,

17. 日射圖 ,

18. 樹，以及

19. 三角蜂窩銳角騎士圖。

火柴圖既是平面的又是單位距離的，但是如果無法構建同時具有這兩種屬性的單一嵌入，則平面單位距離圖可能不是火柴圖。例子包括稜柱圖 和 Moser 紡錘體。唯一的 6 頂點連通平面單位距離非火柴圖是 3-稜柱圖 。在 , 2, ... 個頂點上，既是平面又是單位距離但不是火柴圖的連通圖的數量是 0, 0, 0, 0, 0, 1, 11, ... (E. Weisstein, 2022 年 1 月 2 日)，其中 7 頂點示例如上圖所示。

考慮最小的 -正則火柴圖，它們是頂點度為 的最小可能的正則火柴圖。因此，最小的 1-正則火柴圖是路徑圖 ，最小的 2-正則火柴圖是三角形圖 ，最小的 3-正則火柴圖是上面所示的 8 頂點圖。最小已知的 4-正則火柴圖是 Harborth 圖，它有 104 條邊和 52 個頂點 (Hartsfield and Ringel 1994; Timm)。雖然 Harborth 圖尚未被證明是最優的，但 Kurz 和 Pinchasi (2011) 表明，平面中每個 4-正則火柴圖至少包含 20 個頂點。最小已知的 -正則火柴圖如上圖所示，並在下表中進行了總結。

多年來，已經出現了幾個關於不存在五次火柴圖的未發表證明（參見 Friedman 2005）。Kurz 和 Pinchasi (2011) 透過證明不存在五次火柴圖解決了這個問題。由於尤拉多面體公式意味著對於 >5，不存在 -正則火柴圖 (Kurz 2014)，這確定了對於 ，不存在此類圖。

最小的（或者，在 Harborth 圖的情況下，推測的最小的）正則火柴圖在 Wolfram 語言中實現為GraphData["MinimalRegularMatchstick", n].

Winkler et al. (2017) 考慮了每個頂點的度數為 或 的小型火柴圖，以及比上面所示的 Harborth 圖稍大的其他四次火柴圖。

最小的 3-正則火柴圖的二部雙圖是 8-交叉稜柱圖。