火柴图

火柴图是一个简单图，它具有一个图嵌入，该嵌入是平面的，其中所有顶点之间的距离都是单位距离，并且是非退化的（因此没有顶点重合，没有边交叉或重叠，也没有顶点与其不关联的边重合）。

在 条边上找到拓扑上不同的火柴图的数量的问题被称为火柴问题（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-交叉棱柱图。