ペニーグラフ

ペニーグラフ (penny graph) とは、平面グラフの一種で、平面上に単位円盤（あるいは与えられた大きさの半径の円盤）を互いに重なり合わないように配置したときに、各円盤の中心を頂点とし、互いに接している円盤の中心同士を辺で結んだものをいう。
これは、マッチ棒グラフのうち、すべての頂点の距離が$1$以上であるものに相似である。なお、本項では、「距離」は平面上のEuclid距離をいう。
また、平面グラフの一種で、辺で結ばれている頂点同士の距離がつねに、（辺で結ばれていないものも含めた）任意の$2$頂点間の距離の中の最小値に一致しているものということもできる。それで、ペニーグラフを最小距離グラフ (minimum distance graph) ともいう。

以下、ペニーグラフの各辺の長さを $1$ とする（半径 $1/2$ の円盤を互いに重なり合わないように配置することに相当する）。

例と基本的性質

六角格子（正三角格子）や正方形格子はペニーグラフである。また、ペニーグラフの部分グラフは明らかにペニーグラフである。

ペニーグラフの各頂点の次数は $6$ 以下である。というのは、ペニーグラフのある頂点 $v$ の次数が $k\geq 7$ のとき、$v$ に隣接する頂点を左回り（あるいは右回り）に $w_0, \ldots, w_{k-1}$ とおくと、ある $i$ について $w_i, v, w_{i+1}$ （ここでは $w_k=w_0$ とおく）のなす角 $\theta$ が $2\pi/7$ 以下となるが、このとき $w_i, w_{i+1}$ の距離が $\abs{w_i w_{i+1}}=2\sin\theta<1$ となって矛盾するからである。

最大の辺の個数

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

$n$ 個の頂点からなるペニーグラフの辺の個数の最大値を $B(n)$ とおく。$B(1)=0$ および $B(2)=1$ は明らかである。また、便宜上 $B(0)=0$ と定める。

$B(n)\leq\floor{3n-\sqrt{12n-3}}$ であることは、$n$ に関する数学的帰納法で証明される。そこで、$n\geq 3$ とし、$m< n$ となる $m$ について $B(m)=\floor{3m-\sqrt{12m-3}}$ と仮定する。

$G$ を $n$ 個の頂点からなるペニーグラフで、辺の個数が最大のものとする。とくに、$G$ 上の、距離が $1$ となる $2$ 点はすべて辺で結ばれている。
$$\label{eq1}B(n)=\abs{E(G)}\leq\floor{3n-\sqrt{12n-3}}\tag{1}$$
を示す。

まず、$G$ の連結度が $1$ 以下の場合について示す。

さて、$G$ 上のサイクル $C$ のうち、$C$ で囲まれた領域 $D$ が極大となる、つまり $D$ よりも大きな領域を囲む $G$ 上のサイクルが存在しないものをひとつとる。

この補題から、以下、$D$ の外部に頂点が存在しないとしてよい。

$C$ 上の点の次数は $2$ から $5$ のいずれかとなる。というのは $C$ 上の頂点 $v$ の次数が $6$ のとき、$v$ に隣接する頂点を左回り（あるいは右回り）に $w_0, \ldots, w_5$ とおくと、各 $i$ について $w_i, v, w_{i+1}$ （ここでは $w_6=w_0$ とおく）のなす角は $\pi/3$ となるが、$\abs{w_i v}=\abs{v w_{i+1}}=1$ より、$\abs{w_i w_{i+1}}=1$ となるから、各 $w_i, w_i+1$ も $G$ の辺となる。しかし $D$ の外部には頂点は存在しないから、$w_0, \ldots, w_5$ でつくられる正$6$角形は $D$ に含まれる。よって $v$ は $D$ の内点となって、$C$ 上の点であることに矛盾するからである。

$a=\abs{C}$ とおく。また、$C$ 上の点のうち、次数が $j$ のものの個数を $k_j$ とおくと
$$\label{eq2}a=k_2+k_3+k_4+k_5\tag{2}$$
となる。
$C$ 上の次数 $j$ の頂点 $v$ について、$v$ に隣接する頂点を左回り（あるいは右回り）に $w_0, \ldots, w_{j-1}$ とおくと
各 $i$ について $w_i, v, w_{i+1}$ のなす角は少なくとも $\pi/3$ であるから、領域 $D$ に関する $v$ の内角は少なくとも $(j-1)\pi/3$ となる。
領域 $D$ は多角形で、内角の総和は $(a-2)\pi$ であるから
$$(a-2)\pi\geq (k_2+2k_3+3k_4+4k_5)\pi/3$$
つまり
$$\label{eq3}3a-6\geq k_2+2k_3+3k_4+4k_5\tag{3}$$
となる。\eqref{eq2}, \eqref{eq3} より
$$\label{eq4}k_3+2k_4+3k_5\leq 2a-6\tag{4}$$
となる。

$G$ から $C$ 上の点と、$C$ 上の点から結ばれる辺を取り除くと、位数 $n-a$ のペニーグラフとなる。
$C$ 上の次数 $d$ 頂点 $v$ について、$v$ と $D$ の内点を結ぶ辺の個数は $d-2$ であるから、
$G$ から $C$ 上の点と、$C$ 上の点から結ばれる辺を取り除いたグラフの辺の個数は $B(n)-a-(k_3+2k_4+3k_5)$ に一致する。よって
$$B(n)-a-(k_3+2k_4+3k_5)\leq B(n-a)$$
が成り立つが、\eqref{eq4} から
$$B(n)\leq B(n-a)+3a-6$$
となる。帰納法の仮定より
$$\label{eq5}B(n)\leq 3(n-a)-\sqrt{12(n-a)-3}+3a-6=3n-6-\sqrt{12(n-a)-3}\tag{5}$$
となる。
$f_i$ を $G$ における正$i$角形の面の個数とし、$f$ を $G$ における面の総数（ただし $D$ の外部は含めない）とすると、
$f=f_3+f_4+\cdots$ となり、Eulerの公式から
$$\label{eq6}n+f=n+f_3+f_4+\cdots =B(n)+1\tag{6}$$
となる。
$C$ 上の辺は$1$つの面に接し、$D$ の内点は$2$つの辺に接しているから、すべての面に関する、その面上の辺の個数の総和は
$$a+2(B(n)-a)=3f_3+4f_4+\cdots\geq 3f$$
となる。
\eqref{eq6}から
$$2B(n)-a\geq 3(B(n)+1-n)$$
つまり
$$\label{eq7}n-a\geq B(n)+3-2n\tag{7}$$
となる。
よって\eqref{eq5}から
$$B(n)\leq 3n-6-\sqrt{12B(n)-24n+33}<3n$$
となるから、
$$(B(n)-3n+6)^2\geq 12B(n)-24n+33$$
より
$$B(n)^2-6nB(n)+9n^2-12n+3\geq 0$$
つまり
$$\abs{B(n)-3n}\geq \sqrt{12n-3}$$
となる。$B(n)<3n$ より
$$B(n)\leq 3n-\sqrt{12n-3}$$
となる。$B(n)$ は整数だから \eqref{eq1} が成り立つ。

これにより、数学的帰納法により、各 $n$ について $B(n)\leq\floor{3n-\sqrt{12n-3}}$ が成り立つことが示された。