単位距離グラフ
概要
単位距離グラフ（unit distance graph）とは、頂点を平面上の相異なる点に置き、どの辺の両端も距離がちょうど $1$ になるように描けるグラフのことである。2 つの円周は 2 点以下でしか交わらないので完全二部グラフ $K_{2,3}$ は描けず、このことから $n$ 頂点の単位距離グラフの辺は $O(n^{3/2})$ 本以下になる。平面の点を距離 $1$ の 2 点が違う色になるように塗るのに要る色の数（平面の彩色数）は、Moser スピンドルにより $4$ 以上、三角格子の 7 色の塗り分けにより $7$ 以下であり、下界は計算機を使って $5$ に改良されている。マッチ棒グラフ・ペニーグラフを含むクラスとして、離散幾何学の距離の問題の中心にある。
平面上に有限個の点を置き、距離がちょうど $1$ の 2 点を辺で結ぶとグラフができる。このようにして描けるグラフを 単位距離グラフ という。三角形・正方形・正六角形の周などは描けるが、4 点が互いに距離 $1$ にあるような配置（完全グラフ $K_4$）は平面にはない。どのグラフが描けるかは、平面の幾何（円と円は 2 点以下でしか交わらない、など）で決まる。
単位距離グラフをめぐる問いのうち最も有名なものは、平面のすべての点を色で塗り、距離 $1$ の 2 点がいつも違う色になるようにするには何色が要るか、という Hadwiger–Nelson 問題 である。この最小の色数を平面の彩色数といい、$4$ 以上 $7$ 以下であることは初等的に示せる。この記事では、7 頂点の Moser スピンドルによる下界 $4$ と、三角格子の 7 色の塗り分けによる上界 $7$ を証明する。下界は 2018 年に計算機を用いて $5$ に改良され、正確な値は $5,6,7$ のいずれかである。後半では、$n$ 点の間に距離 $1$ の対がいくつありうるかという Erdős の単位距離問題を扱い、上界 $O(n^{3/2})$ を証明する。
定義
この記事では、$\mathbb{R}^d$ に通常の Euclid 距離 $\lvert x-y\rvert$ を入れる（Euclid空間）。グラフは特に断らない限り有限な単純グラフ $G=(V,E)$ とする。
グラフ $G=(V,E)$ の $\mathbb{R}^d$ への 単位距離表現（unit distance representation）とは、単射 $\varphi\colon V\to\mathbb{R}^d$ であって、各辺 $uv\in E$ について $\lvert\varphi(u)-\varphi(v)\rvert=1$ を満たすものをいう。$\mathbb{R}^2$ への単位距離表現をもつグラフを 単位距離グラフ（unit distance graph）という。$\mathbb{R}^d$ への単位距離表現をもつグラフを $\mathbb{R}^d$ の単位距離グラフという。
単位距離表現 $\varphi$ が、さらに「$uv\notin E$ なら $\lvert\varphi(u)-\varphi(v)\rvert\neq1$」を満たすとき、$\varphi$ は 忠実 であるという。
単位距離表現では、隣接しない 2 頂点の像がたまたま距離 $1$ にあってもよい。マッチ棒グラフ の定義の条件 1 は、この意味の単位距離表現である。文献によっては忠実な表現をもつグラフだけを単位距離グラフと呼ぶので、引用するときは規約を確かめる必要がある。
平面 $\mathbb{R}^2$ のすべての点を頂点とし、距離がちょうど $1$ の 2 点を辺で結んだ無限グラフを $G(\mathbb{R}^2)$ と書く。正の整数 $k$ について、写像 $c\colon\mathbb{R}^2\to\{1,\dots,k\}$ で「$\lvert x-y\rvert=1$ なら $c(x)\neq c(y)$」を満たすものを平面の $k$ 彩色 という。$k$ 彩色が存在する最小の $k$ を 平面の彩色数（chromatic number of the plane）といい、$\chi(\mathbb{R}^2)$ と書く。$\chi(\mathbb{R}^2)$ の値を決める問題を Hadwiger–Nelson 問題 という。
有限グラフ $G$ が単位距離グラフであることは、$G$ が $G(\mathbb{R}^2)$ のある有限部分グラフと同型であることと同じである。忠実な単位距離表現をもつことは、$G(\mathbb{R}^2)$ のある有限誘導部分グラフと同型であることと同じである。平面の $k$ 彩色 $c$ と単位距離表現 $\varphi$ があれば、$c\circ\varphi$ は $G$ の頂点彩色なので、
$$
\chi(G)\le\chi(\mathbb{R}^2)\qquad(G\text{ は有限の単位距離グラフ})
$$
が成り立つ。とくに、彩色数の大きい単位距離グラフを 1 つ見つければ $\chi(\mathbb{R}^2)$ の下界が得られる。
直感
点 $x$ から距離 $1$ の点の全体は、$x$ を中心とする半径 $1$ の円周である。単位距離グラフの辺を加えることは、頂点の像を円周の上に縛ることにあたる。2 つの円周は 2 点以下でしか交わらないので、2 頂点に共通の隣接頂点を 3 つ以上もたせることはできない。この「2 点以下」が、辺の本数の上界（thm-udg-edges）の源である。
彩色の上界は逆に、平面を直径 $1$ 未満の小さな領域に分け、同じ色の領域どうしを $1$ より離して並べれば得られる。三角格子のまわりの正六角形をタイルにして 7 色で塗ると、これが実現できる。下界の側では、正三角形を 2 枚貼り合わせたひし形が要になる。ひし形の両端の頂点は、3 色で塗ろうとすると必ず同じ色になる。共通の頂点のまわりに 2 つのひし形を回して置き、遠い端どうしの距離を $1$ にすると、3 色では塗れなくなる。
例と反例
- 道グラフ $P_n$ は、頂点を $(1,0),(2,0),\dots,(n,0)$ に置けば単位距離グラフである。閉路グラフ $C_n$（$n\ge3$）は、1 辺の長さ $1$ の正 $n$ 角形の頂点に置けば単位距離グラフである。
- 星グラフ $K_{1,n}$（完全二部グラフ）は、中心を原点に、葉を単位円周上の相異なる $n$ 点に置けば単位距離グラフである。したがって単位距離グラフの次数（次数(グラフ)）に上限はない。
- 三角格子（マッチ棒グラフ の定義「三角格子グラフ」）の有限部分集合で距離 $1$ の対を結んだグラフは単位距離グラフであり、ペニーグラフ でもある。
- マッチ棒グラフ はすべて単位距離グラフであり、ペニーグラフ はすべてマッチ棒グラフである（ペニーグラフ の命題「ペニーグラフはマッチ棒グラフである」）。
頂点 $v,a,b,c,d,e,f$ と 11 本の辺
$$
va,\ vb,\ ab,\ ac,\ bc,\quad vd,\ ve,\ de,\ df,\ ef,\quad cf
$$
からなるグラフを Moser スピンドル（Moser spindle）という。正三角形 2 枚からなるひし形 $vacb$ と $vdfe$ が頂点 $v$ を共有し、遠い頂点 $c,f$ が辺で結ばれている。
Moser スピンドルは単位距離グラフである。$\theta:=\arccos(5/6)$ とし、$v$ を原点、$c=(\sqrt3,0)$、$a,b$ を原点から距離 $1$・偏角 $\pm30^\circ$ の点、$f$ を原点から距離 $\sqrt3$・偏角 $\theta$ の点、$d,e$ を原点から距離 $1$・偏角 $\theta\pm30^\circ$ の点に置けばよい。ひし形の辺と短い対角線の長さが $1$ であることは余弦定理からわかり、$\lvert cf\rvert^2=3+3-6\cos\theta=1$ である（7 点が相異なることも含めた確認は マッチ棒グラフ の例「反例：Moser スピンドル」にある）。
性質
- 単位距離グラフの任意の部分グラフは単位距離グラフである。
- 2 つの単位距離グラフの非交和は単位距離グラフである。
- 単位距離表現を部分グラフの頂点集合に制限すれば、単射で、部分グラフの辺の両端の距離は $1$ である。(2) $\varphi_1,\varphi_2$ をそれぞれの単位距離表現とし、$\varphi_2$ を十分遠くへ平行移動して像を $\varphi_1$ の像と交わらないようにすれば、合わせた写像は単射で、各辺の両端の距離は $1$ のままである。$\square$
忠実な表現では (1) は誘導部分グラフについてしか言えない。この記事の規約で部分グラフについて閉じているのは、隣接しない頂点の距離を問わないからである。
相異なる 2 点 $y,z\in\mathbb{R}^2$ について、$\lvert x-y\rvert=\lvert x-z\rvert=1$ を満たす点 $x\in\mathbb{R}^2$ は 2 個以下である。
$\lvert x-y\rvert=\lvert x-z\rvert$ より、$x$ は線分 $yz$ の垂直二等分線の上にある。中点を $M$、$z-y$ に直交する単位ベクトルを $u$ とすると $x=M+tu$（$t\in\mathbb{R}$）と書け、$h:=\lvert y-z\rvert/2$ とおくと三平方の定理により $\lvert x-y\rvert^2=h^2+t^2$ である。これが $1$ に等しいのは $t^2=1-h^2$ のときだけなので、$t$ は 2 個以下である。$\square$
単位距離グラフの相異なる 2 頂点に共通の隣接頂点は 2 個以下である。とくに完全二部グラフ $K_{2,3}$ は単位距離グラフでない。
単位距離表現 $\varphi$ のもとで、$y,z$ に共通の隣接頂点 $x$ の像は $\varphi(y),\varphi(z)$ の両方から距離 $1$ にある。lem-udg-two-circles によりそのような点は 2 個以下で、$\varphi$ は単射だから、共通の隣接頂点も 2 個以下である。$\square$
平面の彩色数
Moser スピンドル（ex-udg-moser）の彩色数は $4$ である。
3 色で塗れたとする。三角形 $vab$ の 3 頂点は相異なる色をもつ。$c$ は $a,b$ の両方に隣接するので、$c$ の色は $a,b$ の色と異なり、残りの 1 色、すなわち $v$ の色である。同じく三角形 $vde$ と $f$ を見ると、$f$ の色も $v$ の色である。$c$ と $f$ は隣接するので矛盾する。よって彩色数は $4$ 以上である。逆に $v,c\mapsto1$、$a,d\mapsto2$、$b,e\mapsto3$、$f\mapsto4$ と塗れば 11 本の辺の両端はすべて違う色になるので、彩色数は $4$ である。$\square$
上界のために、三角格子の点を 7 色に塗り分ける。$p:=(1,0)$、$q:=(1/2,\sqrt3/2)$ とおくと $\lvert p\rvert=\lvert q\rvert=1$、内積は $p\cdot q=1/2$ なので、整数 $a,b$ について
$$
\lvert ap+bq\rvert^2=a^2+ab+b^2
$$
である。$d>0$ について $\Lambda_d:=\{d(mp+nq)\mid m,n\in\mathbb{Z}\}$ とおく。$p,q$ は一次独立なので、$\Lambda_d$ の点の $(m,n)$ は一意に決まる。
任意の点 $x\in\mathbb{R}^2$ について、$\lvert x-c\rvert\le d/\sqrt3$ となる $c\in\Lambda_d$ が存在する。
要点：平面は 1 辺 $d$ の正三角形で格子点を頂点として敷き詰められ、正三角形の各点は最も近い頂点から外接円の半径 $d/\sqrt3$ 以内にある。
詳細
$x=d(sp+tq)$ と書き、$m:=\lfloor s\rfloor$、$n:=\lfloor t\rfloor$、$\sigma:=s-m$、$\tau:=t-n\in[0,1)$、$A:=d(mp+nq)$ とおく。$\sigma+\tau\le1$ なら $x=(1-\sigma-\tau)A+\sigma(A+dp)+\tau(A+dq)$ は 3 点 $A,A+dp,A+dq$ の凸結合である。$\sigma+\tau>1$ なら $\sigma':=1-\sigma$、$\tau':=1-\tau$ とおくと $\sigma'+\tau'<1$ で、$x=(1-\sigma'-\tau')(A+dp+dq)+\tau'(A+dp)+\sigma'(A+dq)$ である。どちらの 3 点も、差が $\pm dp,\pm dq,\pm d(q-p)$ なので 1 辺 $d$ の正三角形の頂点である。
1 辺 $d$ の正三角形 $ABC$ の外心を $O$、外接円の半径を $r=d/\sqrt3$ とする。三角形 $ABC$ は 3 つの三角形 $OAB$、$OBC$、$OCA$ の和であり、$OAB$ は $AB$ の中点 $M$ と $O$ を結ぶ線分で $OAM$ と $OMB$ に分かれる。$OAM$ の 3 頂点は $A$ から距離 $r$、$d/2$、$0$ にあってどれも $r$ 以下であり、$A$ を中心とする半径 $r$ の閉円板は凸なので、$OAM$ 全体がこの円板に含まれる。ほかの 5 つの小三角形も同様である。よって $x$ は 3 頂点のどれかから距離 $r$ 以内にある。$\square$
$\kappa\colon\Lambda_d\to\mathbb{Z}/7\mathbb{Z}$ を $\kappa(d(mp+nq)):=m+3n\bmod 7$ で定める。$\kappa(c)=\kappa(c')$ となる相異なる $c,c'\in\Lambda_d$ について $\lvert c-c'\rvert\ge\sqrt7\,d$ である。
$c-c'=d(ap+bq)$、$(a,b)\neq(0,0)$ とおくと $a+3b\equiv0\pmod 7$ であり、$\lvert c-c'\rvert^2=d^2Q$、$Q:=a^2+ab+b^2$ である。$Q<7$ となる $(a,b)$ がすべて $a+3b\not\equiv0$ を満たすことを示せばよい。$4Q=(2a+b)^2+3b^2$ なので、$Q<7$ なら $3b^2<28$、すなわち $\lvert b\rvert\le3$ である。$(a,b)$ と $(-a,-b)$ は同時に考えてよいので $b\ge0$ とする。
詳細
$b=3$ なら $(2a+3)^2<1$ となる整数 $a$ はない。$b=2$ なら $(2a+2)^2<16$ より $a\in\{-2,-1,0\}$ で、$a+3b=4,5,6$。$b=1$ なら $(2a+1)^2<25$ より $a\in\{-2,-1,0,1\}$ で、$a+3b=1,2,3,4$。$b=0$ なら $4a^2<28$ かつ $a\neq0$ より $a=\pm1,\pm2$ で、$a+3b=\pm1,\pm2$。どれも $7$ の倍数でない。
よって $Q\ge7$ であり、$\lvert c-c'\rvert\ge\sqrt7\,d$ である。$\square$
$$ 4\le\chi(\mathbb{R}^2)\le7. $$
下界：Moser スピンドルは単位距離グラフであり（ex-udg-moser）、彩色数は $4$ である（prop-udg-moser-chromatic）。定義の後で見たとおり $\chi(G)\le\chi(\mathbb{R}^2)$ なので、$\chi(\mathbb{R}^2)\ge4$ である。
上界：$d:=4/5$、$r:=d/\sqrt3$ とおく。各点 $x\in\mathbb{R}^2$ について、lem-udg-covering により $\lvert x-c(x)\rvert\le r$ となる格子点 $c(x)\in\Lambda_d$ を 1 つ選び（候補は有限個なので、たとえば最も近いもののうち $(m,n)$ が辞書式で最小のもの）、$x$ に色 $\kappa(c(x))$ を与える（lem-udg-seven）。これは 7 色の塗り分けである。$x,y$ が同じ色をもつとする。$c(x)=c(y)$ なら
$$
\lvert x-y\rvert\le\lvert x-c(x)\rvert+\lvert c(y)-y\rvert\le2r=\frac{8}{5\sqrt3}<1
$$
である（$64<75$）。$c(x)\neq c(y)$ なら lem-udg-seven により $\lvert c(x)-c(y)\rvert\ge\sqrt7\,d$ なので、
$$
\lvert x-y\rvert\ge\sqrt7\,d-2r=\frac{1}{5}\Bigl(4\sqrt7-\frac{8}{\sqrt3}\Bigr)>\frac{1}{5}(10.5-4.7)>1
$$
である（$16\cdot7=112>10.5^2$、$64/3<4.7^2$）。どちらの場合も $\lvert x-y\rvert\neq1$ なので、これは平面の 7 彩色であり、$\chi(\mathbb{R}^2)\le7$ である。$\square$
格子点 $c\in\Lambda_d$ に最も近い点の全体は、$c$ を中心とする 1 辺 $d/\sqrt3$ の正六角形である。上の塗り分けは、正六角形の敷き詰めの各タイルを $7$ 色で塗り、同じ色のタイルどうしをタイルの直径より遠くに置いたものにあたる。
上の評価は次のように改良されている。この記事では証明しない。
彩色数が $5$ の有限の単位距離グラフが存在する。したがって $\chi(\mathbb{R}^2)\ge5$ である。
thm-udg-de-grey は de Grey が 2018 年に示した（dG18）。同論文が示した最小の例は $1581$ 頂点のグラフで、4 色で塗れないことの確認には計算機を用いる。同論文の導入によれば、上界 $7$ は 1950 年に Isbell が六角形の塗り分けで、下界 $4$ は Nelson が与えていた。
選択公理のもとで、無限グラフの有限部分グラフがすべて $k$ 色で塗れるなら全体も $k$ 色で塗れる（de Bruijn–Erdős の定理、dBE51 Theorem 1）。これを $G(\mathbb{R}^2)$ に当てはめると、$\chi(\mathbb{R}^2)$ は有限の単位距離グラフの彩色数の最大値に等しい。thm-udg-hadwiger-nelson と合わせて $\chi(\mathbb{R}^2)\in\{5,6,7\}$ であり、どれに等しいかは未解決である。
辺の本数
$n$ 点の間に距離 $1$ の対がいくつありうるかを考える。$n\ge1$ について
$$
u(n):=\max\bigl\{\#\{\{x,y\}\subset P\mid\lvert x-y\rvert=1\}\ \bigm|\ P\subset\mathbb{R}^2,\ \lvert P\rvert=n\bigr\}
$$
とおく。この記事の規約では、$u(n)$ は $n$ 頂点の単位距離グラフの辺の本数の最大値に等しい。
$n$ 頂点の単位距離グラフの辺は
$$
\frac{n}{4}\bigl(1+\sqrt{8n-7}\bigr)\le\frac{n}{4}+\frac{n^{3/2}}{\sqrt2}
$$
本以下である。とくに $u(n)=O(n^{3/2})$ である。
単位距離表現で頂点を点と同一視し、頂点 $x$ の次数（$x$ に隣接する頂点の個数）を $d_x$、辺の本数を $m$ とする。$\sum_xd_x=2m$ である。頂点 $x$ と、$x$ に隣接する相異なる 2 頂点 $\{y,z\}$ の組の個数 $T$ を 2 通りに数える。$x$ ごとに数えれば $T=\sum_x\binom{d_x}{2}$ である。$\{y,z\}$ ごとに数えれば、cor-udg-k23 により $x$ は 2 個以下なので $T\le2\binom n2=n(n-1)$ である。一方、Cauchy–Schwarzの不等式 により $\sum_xd_x^2\ge(\sum_xd_x)^2/n=4m^2/n$ なので
$$
T=\frac12\Bigl(\sum_xd_x^2-\sum_xd_x\Bigr)\ge\frac{2m^2}{n}-m.
$$
合わせて $2m^2-nm-n^2(n-1)\le0$ となり、2 次不等式を解いて
$$
m\le\frac{n+\sqrt{n^2+8n^2(n-1)}}{4}=\frac n4\bigl(1+\sqrt{8n-7}\bigr)
$$
を得る。$\sqrt{8n-7}<2\sqrt2\sqrt n$ から右側の不等式が出る。$\square$
下からの評価には超立方体が使える。$k\ge1$ について、$\{0,1\}^k$ を頂点とし、ちょうど 1 つの座標が異なる 2 点を辺で結んだグラフを $k$ 次元超立方体グラフ $Q_k$ という。頂点は $2^k$ 個、辺は $k2^{k-1}$ 本である。
任意の $k\ge1$ について $Q_k$ は単位距離グラフである。したがって $u(2^k)\ge k2^{k-1}$、すなわち $n=2^k$ のとき $u(n)\ge\frac n2\log_2n$ である。
要点：相異なる単位ベクトル $v_1,\dots,v_k$ を「和 $\sum_i\varepsilon_iv_i$（$\varepsilon\in\{0,1\}^k$）が相異なる」ように選び、$\varepsilon\mapsto\sum_i\varepsilon_iv_i$ とすればよい。1 つの座標 $i$ だけが異なる 2 点の像の差は $\pm v_i$ で、長さは $1$ である。
詳細
和が相異なることは、$\delta\in\{-1,0,1\}^k$、$\delta\neq0$ について $\sum_i\delta_iv_i\neq0$ となることと同値である。$v_j=(\cos\theta_j,\sin\theta_j)$ を $j=1,2,\dots$ の順に選ぶ。$\delta_j\neq0$ で $\delta_i=0$（$i>j$）の $\delta$ について、条件は $v_j\neq-\delta_j\sum_{i< j}\delta_iv_i$ である（$\delta_j=\pm1$）。$(\delta_1,\dots,\delta_{j-1})$ は $3^{j-1}$ 通りなので、禁じられる単位ベクトルは有限個であり、それを避けて $\theta_j$ を選べる。最後の非零の座標が $j$ である $\delta$ はすべて $j$ 番目の段で処理されるので、選び終えたとき条件はすべての $\delta\neq0$ について成り立つ。$\square$
Erdős は 1946 年に、正方格子の一部を適当な縮尺で使って $u(n)>n^{1+c/\log\log n}$（$c>0$ は定数）となることを数論の結果から導き、上界 $u(n)< n^{3/2}$ を示した（Erd46 Theorem 2。下界の証明は概略）。上界は Spencer・Szemerédi・Trotter により $u(n)\le Cn^{4/3}$ に改良され、Székely は円弧で描いたグラフに交差数補題（交差数(グラフ)）を当てる短い証明を与えた（Sze97）。Erdős は $u(n)\le n^{1+o(1)}$ を予想しており、2026 年現在未解決である。この記事ではこれらを証明しない。
反例の表
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 別の色を要求するのは距離がちょうど $1$ の 2 点だけ（thm-udg-hadwiger-nelson の上界） | 距離 $1$ 以下の 2 点をすべて別の色にする | 有限個の色では塗れない。直径 $1$ の円板の中の点は互いに距離 $1$ 以下なので、無限個の点がすべて違う色を要する |
| 平面（2 次元）（thm-udg-hadwiger-nelson の下界） | 直線 $\mathbb{R}$ で同じ問題を考える | $x\mapsto\lfloor x\rfloor\bmod2$ は距離 $1$ の 2 点に違う色を与えるので、2 色で足りる。下界 $4$ は成り立たない |
| 平面（2 次元）（thm-udg-edges） | $\mathbb{R}^4$ の点 $(\frac{\cos\alpha_i}{\sqrt2},\frac{\sin\alpha_i}{\sqrt2},0,0)$ と $(0,0,\frac{\cos\beta_j}{\sqrt2},\frac{\sin\beta_j}{\sqrt2})$ | 2 組の点の間の距離はすべて $1$ なので、完全二部グラフ $K_{s,t}$ が $\mathbb{R}^4$ の単位距離グラフになる。$n$ 点で $\lfloor n/2\rfloor\lceil n/2\rceil$ 本の辺が得られ、上界 $O(n^{3/2})$ は成り立たない |
補足
単位距離グラフは、平面に描いたときの制約の強さで次のように並ぶ。ペニーグラフ は硬貨を重ならないように並べた接触グラフで、マッチ棒グラフ は長さ $1$ の棒を交差させずに並べたグラフである。包含関係は「ペニーグラフ ⊂ マッチ棒グラフ ⊂ 単位距離グラフ」で、どちらの包含も真である（星グラフ $K_{1,7}$、Moser スピンドル）。距離が $1$ に等しい対ではなく $1$ 以下の対を結ぶと 単位円板グラフ になる。単位円板グラフでは完全グラフ $K_4$ が描けるが星グラフ $K_{1,6}$ は描けず、単位距離グラフとは包含関係にない。
単位距離グラフの問題は、点の配置と距離の個数を数える離散幾何学の中心的な話題の 1 つである。相異なる距離の個数についての Erdős の問題も同じ論文 Erd46 に始まる。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
