マッチ棒グラフ

道グラフ $P_n$ は、頂点 $1,\dots,n$ を点 $(i,0)$ に置けばマッチ棒グラフである。各辺 $\{i,i+1\}$ の線分 $[(i,0),(i+1,0)]$ は長さ $1$ であり、相異なる線分は共通の端点以外で交わらず、頂点は接続しない辺の上にない。閉路グラフ $C_n$（$n\ge3$）は、1 辺の長さ $1$ の正 $n$ 角形の頂点を順に頂点 $1,\dots,n$ に対応させればマッチ棒グラフである。正 $n$ 角形は凸多角形なので、その辺は共通の端点以外で交わらず、頂点はどの辺の内部にもない。

星グラフ $K_{1,n}$（完全二部グラフ）は任意の $n\ge1$ についてマッチ棒グラフである。中心の頂点を原点に置き、$n$ 個の葉を単位円周上の相異なる点 $(\cos(2\pi k/n),\sin(2\pi k/n))$（$k=0,\dots,n-1$）に置けばよい。各辺は原点から単位円周上の点への長さ $1$ の線分であり、相異なる 2 本は原点でのみ交わり、葉は他の辺の上にない。したがってマッチ棒グラフの最大次数（次数(グラフ)）に上限はない。$n\ge7$ のとき、隣り合う葉の距離は $2\sin(\pi/n)<1$ であり、この表現の頂点は距離 $1$ 未満で近づいている。

$A:=(-1/2,0)$、$B:=(1/2,0)$、$C:=(0,\sqrt{3}/2)$、$D:=(0,-\sqrt{3}/2)$ とおく。三角形 $ABC$、$ABD$ は 1 辺の長さ $1$ の正三角形であり、辺 $AB,AC,BC,AD,BD$ からなる 4 頂点のグラフ（ひし形の 4 辺と短い対角線）を $Q$ とする。$t:=(\sqrt{3}/2,1/2)$（$|t|=1$）とおき、$A':=A+t$、$B':=B+t$、$C':=C+t$、$D':=D+t$ を頂点、$A'B',A'C',B'C',A'D',B'D'$ を辺とする $Q$ の平行移動を $Q'$ とする。$Q\cup Q'$ に 2 本の辺 $CC'$、$DD'$ を加えたグラフ $G$ は、8 個の頂点と 12 本の辺を持つ $3$-正則グラフであり、上の座標がそのマッチ棒表現を与える。
実際、すべての辺の長さは $1$ である（$CC'$、$DD'$ の長さは $|t|=1$）。一次式 $\ell(x,y):=\sqrt{3}x+y$ は $Q$ の頂点で最大値 $\sqrt{3}/2$（$B,C$ で達成）をとり、$Q'$ の頂点では $\ell$ の値が $\ell(t)=2$ だけ大きいので最小値 $-\sqrt{3}/2+2>\sqrt{3}/2$ をとる。よって直線 $\ell=1$ が $Q$ の頂点・辺と $Q'$ の頂点・辺を分離し、$Q$ の辺と $Q'$ の辺は交わらず、一方の頂点が他方の辺の上にあることもない。辺 $CC'$ の点は $y$ 座標が $\sqrt{3}/2$ 以上であり、$CC'$ と端点を共有しない辺 $AB,AD,BD,A'B',A'D',B'D'$ と頂点 $A,B,D,A',B',D'$ はすべて $y$ 座標が $1/2$ 以下なので、$CC'$ はそれらと交わらない。$CC'$ と端点を共有する辺 $AC,BC,A'C',B'C'$ は $CC'$ と平行でないので、共有する端点以外では交わらない。辺 $DD'$ についても同様に、その点の $y$ 座標は $1/2-\sqrt{3}/2$ 以下で、端点を共有しない辺と頂点はすべて $y$ 座標が $0$ 以上なので交わらず、端点を共有する辺 $AD,BD,A'D',B'D'$ とは平行でない。$CC'$ と $DD'$ も $y$ 座標の範囲が離れているので交わらない。以上により、これはマッチ棒表現である。

$s\ge1$ を整数とし、三角格子グラフのうち、原点を中心とする 1 辺の長さ $s$ の正六角形（頂点 $sp,sq,s(q-p),-sp,-sq,-s(q-p)$）の内部と周上にある格子点を頂点とし、その間の距離 $1$ の対をすべて辺とする有限グラフを $H_s$ とする。$H_s$ はマッチ棒グラフであり、頂点数は $3s^2+3s+1$、辺数は $9s^2+3s$ である。
実際、$H_s$ の辺は正六角形を 1 辺の長さ $1$ の正三角形 $6s^2$ 個に分割する三角形分割の辺であり、三角形分割の 2 辺は共通の端点以外で交わらず、頂点は辺の内部にないので、包含写像 $\Lambda\supset V(H_s)\to\mathbb{R}^2$ がマッチ棒表現である。頂点数は、原点から格子距離 $k$（$1\le k\le s$）の格子点がちょうど $6k$ 個あることから $1+\sum_{k=1}^{s}6k=3s^2+3s+1$ である。辺数は、各正三角形が 3 辺を持ち、六角形の周上の $6s$ 本の辺はちょうど 1 個の三角形に、内部の辺はちょうど 2 個の三角形に属することから、$3\cdot6s^2=6s+2\bigl(|E(H_s)|-6s\bigr)$、すなわち $|E(H_s)|=9s^2+3s$ である。
$n=3s^2+3s+1$ のとき $12n-3=36s^2+36s+9=(6s+3)^2$ なので
$$3n-\sqrt{12n-3}=9s^2+9s+3-(6s+3)=9s^2+3s=|E(H_s)|$$
であり、$H_s$ は thm-matchstick-edge-bound の上界を等号で達成する。$H_s$ の頂点間の距離はすべて $1$ 以上であり、距離 $1$ の対はすべて辺なので、$H_s$ はペニーグラフでもある。

Harborth は 1986 年に、52 個の頂点と 104 本の辺を持つ $4$-正則なマッチ棒グラフを構成した（Har94）。これは Harborth グラフ（Harborth graph）とよばれ、2026 年 9 月現在、$4$-正則マッチ棒グラフとして知られている中で最小のものである。$4$-正則マッチ棒グラフの頂点数の最小値は 2026 年 9 月現在確定しておらず、$20$ 以上であることが知られている（KP11）。

完全グラフ $K_4$ は平面グラフであるが、マッチ棒グラフではない。実際、$K_4$ は単位距離グラフですらない。4 点 $a,b,c,d\in\mathbb{R}^2$ のすべての対の距離が $1$ であるとすると、$a,b,c$ は 1 辺の長さ $1$ の正三角形をなす。$a,b$ の両方から距離 $1$ にある点は、$a,b$ を中心とする 2 つの単位円周の交点であり、それは $c$ と、直線 $ab$ に関する $c$ の鏡像 $c'$ のちょうど 2 点である。$d\neq c$ だから $d=c'$ であるが、$|c-c'|=2\cdot\frac{\sqrt{3}}{2}=\sqrt{3}\neq1$ となり矛盾する。満たす性質：平面グラフである。満たさない性質：単位距離グラフである（したがってマッチ棒グラフである）。破る含意：「平面グラフ ⇒ マッチ棒グラフ」は成り立たない。

頂点 $v,a,b,c,d,e,f$ と 11 本の辺
$$va,\ vb,\ ab,\ ac,\ bc,\quad vd,\ ve,\ de,\ df,\ ef,\quad cf$$
からなるグラフを Moser スピンドル（Moser spindle）という（MM61）。これは頂点 $v$ を共有する 2 つのひし形 $vacb$、$vdfe$（それぞれ 2 つの正三角形からなる）の遠い頂点 $c,f$ を辺で結んだものである。Moser スピンドルは平面グラフであり、単位距離グラフでもあるが、マッチ棒グラフではない。
平面グラフであること：$v=(0,0)$、$a=(1,1)$、$c=(2,0)$、$b=(1,-1)$、$d=(-1,1)$、$f=(-2,0)$、$e=(-1,-1)$ とおいて 10 本の辺を線分で描き、辺 $cf$ を折れ線 $c,(2,2),(-2,2),f$ で描けば交差しない。
単位距離グラフであること：$\theta:=\arccos(5/6)$ とおく。$\cos60^\circ=1/2<5/6<\cos30^\circ=\sqrt{3}/2$ だから $30^\circ<\theta<60^\circ$ である。$v=(0,0)$、$c=(\sqrt{3},0)$、$a,b$ を原点から距離 $1$、偏角 $\pm30^\circ$ の点、$f$ を原点から距離 $\sqrt{3}$、偏角 $\theta$ の点、$d,e$ を原点から距離 $1$、偏角 $\theta+30^\circ$、$\theta-30^\circ$ の点とする。三角形 $vac$ は $|va|=1$、$|vc|=\sqrt{3}$、$\angle avc=30^\circ$ だから余弦定理により $|ac|^2=1+3-2\sqrt{3}\cos30^\circ=1$ であり、同様に $|bc|=|df|=|ef|=1$ である。$|ab|=|de|=2\sin30^\circ=1$ であり、$|cf|^2=3+3-6\cos\theta=1$ である。7 点は相異なる（$v$ 以外の 6 点の偏角と距離の組が相異なる。$e$ の偏角 $\theta-30^\circ$ は $0^\circ$ と $30^\circ$ の間にあり、$d$ の偏角は $60^\circ$ と $90^\circ$ の間にある）ので、これは単位距離グラフとしての表現である。
マッチ棒グラフでないこと：$\varphi$ をマッチ棒表現と仮定して矛盾を導く。以下、頂点とその像を同一視する。三角形 $vab$ は 1 辺の長さ $1$ の正三角形であり、$a,b$ の両方から距離 $1$ にある点は $v$ とその鏡像の 2 点だから、$\varphi$ の単射性により $c$ は直線 $ab$ に関する $v$ の鏡像であり、$|vc|=\sqrt{3}$ である。同様に $|vf|=\sqrt{3}$ であり、$|cf|=1$ だから余弦定理により $\cos\angle cvf=5/6$、すなわち $\angle cvf=\theta$ である。したがって、必要なら合同変換（回転・鏡映）で動かして、上の単位距離表現と同じ配置にできる。すなわち $c$ は偏角 $0^\circ$、$a,b$ は偏角 $\pm30^\circ$、必要なら $d$ と $e$ の名前を入れ替えて（グラフの自己同型）、$e$ は偏角 $\theta-30^\circ\in(0^\circ,30^\circ)$ で原点から距離 $1$、$f$ は偏角 $\theta\in(30^\circ,60^\circ)$ で原点から距離 $\sqrt{3}$ の点である。
ひし形 $R:=$（$v,a,c,b$ の凸包）を考える。$R$ は頂点 $v$ における内角が $60^\circ$ の凸四角形であり、その周は辺 $va,ac,cb,bv$ の線分からなり、$R$ は偏角が $-30^\circ$ 以上 $30^\circ$ 以下の点だけからなる。$f$ の偏角は $30^\circ$ より大きいので $f\notin R$ である。一方、偏角 $\phi\in(0^\circ,30^\circ)$ の原点からの半直線は、$R$ の周のうち線分 $ac$ 上の点で $R$ から出る。原点から直線 $ac$ への距離は $\sqrt{3}/2$ であり、垂線の足の偏角は $60^\circ$ だから、この半直線が直線 $ac$ と交わる点の原点からの距離は $(\sqrt{3}/2)/\cos(60^\circ-\phi)$ であり、$60^\circ-\phi\in(30^\circ,60^\circ)$ より $\cos(60^\circ-\phi)<\sqrt{3}/2$ なので、この距離は $1$ より大きい。よって半直線上の原点からの距離 $1$ の点 $e$ は $R$ の内点である。
線分 $[e,f]$ は $R$ の内点 $e$ から $R$ の外の点 $f$ に至るので、$R$ の周上の点 $z$ を通る。$z$ は線分 $va,ac,cb,bv$ のいずれかの上にあり、$z\neq e,f$ である。$z$ が $v,a,b,c$ のいずれかなら、頂点 $z$ が接続しない辺 $ef$ の線分上にあることになり条件 3 に反する。そうでなければ、辺 $ef$ と、$va,ac,cb,bv$ のうち $z$ を含む辺とが、共通の端点でない点 $z$ で交わることになり条件 2 に反する（$\{e,f\}\cap\{v,a,b,c\}=\emptyset$）。いずれにせよ矛盾であり、Moser スピンドルはマッチ棒グラフではない。
満たす性質：平面グラフであり、かつ単位距離グラフである。満たさない性質：マッチ棒グラフである。破る含意：「平面グラフかつ単位距離グラフ ⇒ マッチ棒グラフ」は成り立たない。平面性と単位距離性は、それぞれ別々の描画で実現できても、同一の描画で同時には実現できないことがある。