マッチ棒グラフ

マッチ棒グラフ (matchstick graph) とは、平面グラフの一種で、すべての辺が単位線分（あるいは与えられた長さの線分）となるものをいう。マッチ棒グラフは単位距離グラフの一種である。

また、マッチ棒グラフの中でも、すべての頂点の距離が$1$以上であるものをペニーグラフという。なお、本項では、「距離」は平面上のEuclid距離をいう。

$\abs{\mathbf{p}}=\abs{\mathbf{q}}$ のとき、ひし形を基本平行四辺形にもつ格子
$$\Lambda=\{m\mathbf{p}+n\mathbf{q}, m, n\in \Z\}$$
は $m, n\in\Z$ について $m\mathbf{p}+n\mathbf{q}$ と $(m+1)\mathbf{p}+n\mathbf{q})$ および $m\mathbf{p}+n\mathbf{q}$ と $m\mathbf{p}+(n+1)\mathbf{q})$ を線分で結ぶことでマッチ棒グラフとなる。とくに正方格子 $\mathbf{p}=(0, 1)$, $\mathbf{q}=(1, 0)$ や六角格子（正三角格子） $\mathbf{p}=(0, 1)$, $\mathbf{q}=(\sqrt{3}/2, 1/2)$ はマッチ棒グラフとなる。

$n$ 個の頂点からなるマッチ棒グラフの辺の個数の最大値は正確に $\floor{3n-\sqrt{12n-3}}$ であることが知られている。$s\in\Z$ のとき、$1$ 辺が長さ $s+1$ の正六角形とその内部に六角格子（正三角格子）状に点を配置し、隣り合う点同士をすべて結ぶと、点の個数は $3s^2+3s+1$, 辺の個数は $9s^2+3s$ となって、最大値を与える。
このことは、ペニーグラフについては Reutterが1972年に予想し 、 Harborthが1974年に証明したが 、任意のマッチ棒グラフについて証明されたのはかなり遅く、 2024年にLavolleeとSwanepeolが証明した 。