Hadwiger–Nelson問題

同義語:Hadwiger-Nelson問題Hadwiger–Nelsonの問題Hadwiger–Nelson problem

概要

Hadwiger–Nelson問題(Hadwiger–Nelson problem)とは、平面の点を色で塗り、距離がちょうど $1$ の 2 点がいつも違う色になるようにするための最小の色数 $\chi(\mathbb{R}^2)$ を求める未解決問題である。上界 $7$ は六角形の塗り分けから、下界 $5$ は有限の単位距離グラフ(de Grey 2018)から得られ、de Bruijn–Erdős の定理により $\chi(\mathbb{R}^2)$ は有限の単位距離グラフの彩色数の最大値に等しい。有理点の平面 $\mathbb{Q}^2$ では $2$ 色で足りる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 単位距離グラフ, 彩色数, Tychonoffの定理

Hadwiger–Nelson問題(Hadwiger–Nelson problem)は、平面のすべての点を色で塗り、距離がちょうど $1$ の 2 点がいつも違う色になるようにするには何色が要るか、を問う未解決問題である。この最小の色数を $\chi(\mathbb{R}^2)$ と書く。問いは 1950 年に Nelson が立てたもので(dG18 §1)、学術誌に掲載された証明で知られている範囲は $5\le\chi(\mathbb{R}^2)\le7$ である。
問題の面白さは、3 つの性質が同時に現れるところにある。第 1 に、上界の塗り分けはタイルの敷き詰めで簡単に書ける。第 2 に、下界は有限個の点の配置だけで決まる(thm-hn-compact)。第 3 に、その有限の配置は、下界 $4$ の 7 頂点から下界 $5$ の 1581 頂点(2018 年)へと一気に大きくなり、計算機なしに扱うのが難しくなる。さらに、点を有理点に制限すると答えは $2$ に落ち(thm-hn-rational)、距離の測り方を変えると $4$ に落ちる(反例の表)。
下界 $4$(Moser スピンドル)と上界 $7$(六角形の塗り分け)の証明は 単位距離グラフ の定理「平面の彩色数の評価」にある。この記事では、そこに無い内容を扱う:下界 $4$ の別の 2 つの見方、有限グラフへの帰着の証明、下界 $5$ の構成の骨組み、次元と点の集合を変えたときの様子である。

問題と到達点

平面の彩色数

正の整数 $k$ について、写像 $c\colon\mathbb{R}^2\to\{1,\dots,k\}$ が平面の $k$ 彩色 であるとは、$\lvert x-y\rvert=1$ なら $c(x)\ne c(y)$ であることをいう。$k$ 彩色が存在する最小の $k$ を 平面の彩色数 といい、$\chi(\mathbb{R}^2)$ と書く。Hadwiger–Nelson 問題 はこの値を決める問題である。色の集合(各色の点の全体)にはどんな正則性も課さない。同じことを $\mathbb{R}^n$ で考えた値を $\chi(\mathbb{R}^n)$ と書く。

$\chi(\mathbb{R}^2)$ は、平面の全点を頂点とし、距離 $1$ の 2 点を辺で結んだ無限グラフの彩色数である。頂点が $\mathbb{R}^2$ の点で、各辺の長さが $1$ であるグラフを単位距離グラフという。単位距離グラフ $G$ について $\chi(G)\le\chi(\mathbb{R}^2)$ である。

問い到達点文献
上界$\chi(\mathbb{R}^2)\le7$Isbell(dG18 §1)。証明は 単位距離グラフ
下界$\chi(\mathbb{R}^2)\ge5$dG18、別証明 EI20
各色が Lebesgue 可測のときの色数 $\chi_m$$\chi_m(\mathbb{R}^2)\ge5$Fal81
可測で距離 $1$ を含まない集合の密度$0.2470$ 以下Amb23
大きい次元$(1.239\ldots+o(1))^n\le\chi(\mathbb{R}^n)\le(3+o(1))^n$Pro18 §1

最後の行の両側の定数の間も未解決である。

2026 年の報告

2026 年 9 月のプレプリント Ope26 は、色の集合に条件を付けない 5 彩色が存在しないこと、すなわち $\chi(\mathbb{R}^2)\ge6$ を主張している。参考文献に挙げた公開の文書は、この主張の Lean による形式化を報告している。可測な条件への還元と幾何の議論からなるもので、計算機で有限グラフを探す従来の方法とは別の道である。Blo26 問題 508(2026 年 10 月 16 日更新)は、これを受けて最良の評価を $6\le\chi\le7$ と記載している。Ope26 は 2026 年 11 月の時点でプレプリントの段階にあるので、この記事は到達点に含めない。主張が正しい場合でも、値が $6$ か $7$ かを決める問題は残る。

3 色では足りないことの 2 つの見方

単位距離グラフ では Moser スピンドルの彩色数から下界 $4$ を出した。同じ下界を、グラフを先に書かずに平面の上で直接示せる。

ひし形の補題

$c$ を平面の 3 彩色とする。$\lvert x-y\rvert=\sqrt3$ なら $c(x)=c(y)$ である。

正三角形 2 枚を貼り合わせる

線分 $xy$ の中点を $M$、$x-y$ に直交する単位ベクトルを $u$ とし、$a:=M+\frac12u$、$b:=M-\frac12u$ とおく。$\lvert a-b\rvert=1$ で、三平方の定理から $\lvert a-x\rvert^2=\frac34+\frac14=1$ である。同じく $a,b$ は $x,y$ のどちらからも距離 $1$ である。$xab$ と $yab$ は 1 辺 $1$ の正三角形なので、$c(a)\ne c(b)$ で、$c(x)$ と $c(y)$ はともに残りの 1 色である。$\square$

平面は 3 色で塗れない

$\chi(\mathbb{R}^2)\ge4$ である。

半径 $\sqrt3$ の円が単色になる

3 彩色 $c$ があるとする。点 $x$ を固定すると、lem-hn-rhombus により $x$ を中心とする半径 $\sqrt3$ の円の上の点はすべて $x$ と同じ色である。この円には長さ $1$ の弦があるので、距離 $1$ の同色の 2 点が見つかる。矛盾である。$\square$

この証明で実際に使った点は有限個である。弦の両端を $p,q$ とし、$x$ と $p$、$x$ と $q$ のそれぞれにひし形を置くと 7 頂点 11 辺のグラフができる。これが Moser スピンドルである。
もう 1 つの小さな例は構成が違う。

Golomb グラフ

原点 $o$、単位円周の上の 6 点 $a_j:=(\cos\frac{j\pi}3,\sin\frac{j\pi}3)$($j=0,\dots,5$)、および半径 $1/\sqrt3$ の円周の上の 3 点 $b_i$($i=0,1,2$)をとる。$b_i$ の偏角は $\delta+\frac{2\pi i}3$ で、$\cos\delta=\frac1{2\sqrt3}$ とする。辺は次の 18 本である。

  • $oa_j$(6 本)と $a_ja_{j+1}$(6 本、添字は $6$ を法とする)
  • $b_0b_1,b_1b_2,b_2b_0$(3 本)
  • $b_ia_{2i}$(3 本)
    10 頂点は相異なり、どの辺も長さ $1$ である。実際、$\lvert a_j-a_{j+1}\rvert=1$ は正六角形の辺で、$\lvert b_i-b_{i'}\rvert=\sqrt3\cdot\frac1{\sqrt3}=1$ である。余弦定理から $\lvert b_i-a_{2i}\rvert^2=1+\frac13-\frac2{\sqrt3}\cos\delta=1$ である。よってこれは単位距離グラフである。
Golomb グラフの彩色数

ex-hn-golomb のグラフの彩色数は $4$ である。

外周の交互の色が三角形を締め出す

3 色で塗れたとする。$o$ の色を $3$ とすると、$a_j$ は色 $1,2$ だけを使う。6 頂点の閉路なので色は交互で、$a_0,a_2,a_4$ は同じ色、たとえば $1$ である。$b_i$ は $a_{2i}$ と隣接するので色 $1$ を使えない。すると三角形 $b_0b_1b_2$ を色 $2,3$ の 2 色で塗ることになり、矛盾である。逆に、$a_0,a_2,a_4\mapsto1$、$a_1,a_3,a_5\mapsto2$、$o\mapsto3$、$b_0\mapsto2$、$b_1\mapsto3$、$b_2\mapsto4$ は 4 彩色である。$\square$

有限グラフへの帰着

de Bruijn–Erdős の定理

$G=(V,E)$ をグラフ(無限でもよい)、$k$ を正の整数とする。$V$ の有限部分集合 $F$ のすべてについて、$F$ で誘導された部分グラフが $k$ 色で塗れるなら、$G$ も $k$ 色で塗れる。

コンパクト性

$X:=\{1,\dots,k\}^V$ に積位相を入れる。$\{1,\dots,k\}$ は有限の離散空間なので、Tychonoffの定理 により $X$ はコンパクトである。有限集合 $F\subset V$ について、$F$ の中の辺の両端で値が違う $c\in X$ の全体を $C_F$ とする。$C_F$ は $F$ の座標だけで決まるので閉集合である。仮定により $F$ の彩色があり、$F$ の外を任意に定めれば $C_F$ の元になるので、$C_F\ne\emptyset$ である。また $C_{F\cup F'}\subset C_F\cap C_{F'}$ なので、$\{C_F\}$ は有限交叉性をもつ。よって $\bigcap_FC_F$ に元 $c$ がある。どの辺 $uv$ についても $c\in C_{\{u,v\}}$ なので、$c$ は $G$ の $k$ 彩色である。$\square$

定理は dBE51 Theorem 1 による。平面の場合の結論を書く。

有限の単位距離グラフで決まる

$\chi(\mathbb{R}^2)$ は、有限の単位距離グラフの彩色数の最大値に等しい。

有限の単位距離グラフの彩色数は $\chi(\mathbb{R}^2)$ 以下で、とくに $7$ 以下なので最大値 $k$ がある。距離 $1$ の点を結ぶ無限グラフの有限部分グラフは単位距離グラフなので $k$ 色で塗れる。thm-hn-compact により平面は $k$ 色で塗れる。$\square$

選択公理と可測性

thm-hn-compact の証明は Tychonoff の定理を無限個の有限空間に使うので、選択公理の弱い形に依存する。得られる塗り分けは構成的でなく、各色が可測である保証もない。各色を可測に限る問題は別の問題で、Fal81 により $5$ 色以上が要る。Amb23 の密度の評価からは、距離 $1$ を含まない可測な 4 個の集合が覆える平面の割合は $4\times0.2470=0.988$ 以下であることが従う。

cor-hn-finite により、下界 $\chi(\mathbb{R}^2)\ge k$ には必ず彩色数 $k$ 以上の有限グラフの証拠がある。ただし、下界を示すのにそのグラフを実際に書き出す必要はない。

下界 5 の構成の骨組み

de Grey の構成(dG18)の出発点は、中心と 1 辺 $1$ の正六角形の頂点からなる 7 頂点 12 辺のグラフ $H$ である。外周の 1 つおきの 3 頂点は 1 辺 $\sqrt3$ の正三角形をなす。これらが同じ色のとき 単色の三つ組 という。

$H$ の 4 彩色の分類

回転・鏡映・色の入れ替えを除いて、$H$ の(高々 4 色の)彩色は次の 4 通りである(外周の色を順に書く)。$121212$、$121213$、$123123$、$123132$。単色の三つ組をもつのは前の 2 つで、後の 2 つはもたない。

外周の色の出方で分ける

中心の色を $4$ とすると、外周は長さ $6$ の閉路の、色 $1,2,3$ による彩色である。同じ色の頂点は隣り合わないので、1 色は高々 3 回現れ、3 回現れるのは 1 つおきの場合である。
ある色が 3 回現れるとする。残りの 3 頂点は互いに隣り合わないので、残りの 2 色で自由に塗れ、$121212$ か $121213$ である。
どの色も 3 回現れないなら、どの色もちょうど 2 回現れる。向かい合う頂点の組で同じ色のものがないとすると、各色の 2 頂点は距離 $2$ で、同じ 1 つおきの三角形の中にある。三角形の頂点は 3 個(奇数)なので、2 個ずつに分けられず矛盾する。よって、ある色、たとえば色 $1$ が向かい合う位置にある。残りの 4 頂点は、向かい合う位置の両側の 2 頂点ずつに分かれ、各組は隣り合うので色 $2,3$ を 1 回ずつ使う。組の並びの 2 通りが $123123$ と $123132$ である。$\square$

構成は次の 2 段からなる(dG18 §1、§3、§4)。
段 1:単色の三つ組を避けられないグラフ $L$. $H$ を 13 個貼り合わせた 31 頂点のグラフ $J$ の 4 彩色で、どの $H$ も単色の三つ組をもたないものは少数に分類される。$J$ を中心のまわりに角 $2\arcsin\frac14$ だけ回したものと合わせた 61 頂点のグラフを $K$ とする。中心から距離 $2$ の点は半径 $2$ の円の上で長さ $1$ の弦だけ動くので、回す前の点と距離 $1$ になる。$K$ のそのような彩色では、中心の反対側にある距離 $4$ の 2 点 $A,B$ が必ず同じ色になる。次に、$K$ を $A$ のまわりに角 $2\arcsin\frac18$ だけ回したものと合わせた 121 頂点のグラフを $L$ とする。$B$ の像 $B'$ は $\lvert B-B'\rvert=1$ を満たす。$A$ が $B$ とも $B'$ とも同じ色なら $B,B'$ が同じ色になって矛盾するので、$L$ のどの 4 彩色でも、52 個の $H$ のどれかが単色の三つ組をもつ。
段 2:単色の三つ組を許さないグラフ $M$. Moser スピンドルの共通の頂点 $v$ と 2 つの遠い頂点 $c,f$ を考える。$c,f$ は隣接するので、距離 $\sqrt3$ の 2 組 $\{v,c\}$、$\{v,f\}$ は同時には単色になれない。単色の三つ組は距離 $\sqrt3$ の単色の組が密集した配置なので、スピンドルを密に含むグラフでは現れにくいと期待できる。de Grey はそのようなグラフとして 1345 頂点のグラフ $M$ を作り、中央の $H$ が単色の三つ組をもつ 4 彩色は存在しないことを計算機で確かめた。
$L$ の 52 個の $H$ のそれぞれに $M$ の複製を貼ると 20425 頂点のグラフ $N$ ができ、段 1 と段 2 から $N$ は 4 色で塗れない。頂点を削ると 1581 頂点まで小さくなる(dG18 §5.1)。その後、SAT ソルバによる削減で 553 頂点(Heu18)、509 頂点 2442 辺(Par22)の例が得られた。EI20 は別の道を通る:4 彩色があれば距離 $\sqrt{11}/3$ の同色の 2 点があり、そこから 1 辺 $1/\sqrt3$ の単色の正三角形が出るが、これを許さない有限グラフがある、という 3 段の議論である。

グラフ頂点数役割
Moser スピンドル7$\chi=4$
Golomb グラフ10$\chi=4$
$H$7単色の三つ組の舞台
$J$、$K$、$L$31、61、121三つ組を強制する
$M$1345三つ組を禁じる
$N$20425$\chi\ge5$
小さくした例1581、553、509$\chi\ge5$

点の集合と次元を変える

平面の下界に現れる配置は $\sqrt3$ のような無理数を座標にもつ。これは偶然ではない。

有理点の平面は 2 色で足りる

$\mathbb{Q}^2$ の点を、距離 $1$ の 2 点が違う色になるように 2 色で塗れる。さらに、$\mathbb{R}^2$ の全点を、差が有理ベクトルである距離 $1$ の 2 点が違う色になるように 2 色で塗れる。

分母が奇数の有理数で考える

$R$ を分母が奇数の有理数の全体とする。$R$ は環で、$\mathbb{Z}$ の奇数と偶数の区別は環準同型 $R\to\mathbb{Z}/2\mathbb{Z}$ に延びる。$\varphi\colon R^2\to\mathbb{Z}/2\mathbb{Z}$ を $\varphi(x,y):=x+y\bmod2$ で定めると、$\varphi$ は群の準同型である。
$(x,y)\in\mathbb{Q}^2$、$x^2+y^2=1$ とする。$x=a/d$、$y=b/d$($a,b,d$ は整数、$d>0$、公約数は $1$ のみ)と書くと $a^2+b^2=d^2$ である。$d$ が偶数なら $a^2+b^2$ は $4$ の倍数で、$a,b$ はともに偶数となり、公約数の条件に反する。よって $d$ は奇数で $(x,y)\in R^2$ である。さらに $a^2+b^2$ は奇数なので $a+b$ は奇数で、$\varphi(x,y)=1$ である。
$\mathbb{Q}^2$ を $R^2$ の剰余類に分け、各剰余類 $C$ に代表元 $z_C$ を選び、$u\in C$ に色 $\varphi(u-z_C)$ を与える。$u,v\in\mathbb{Q}^2$、$\lvert u-v\rvert=1$ なら、上で見たとおり $u-v\in R^2$ で $\varphi(u-v)=1$ である。$u,v$ は同じ剰余類にあり、色は違う。$\mathbb{R}^2$ の場合は、$\mathbb{R}^2$ を加法群の部分群 $R^2$ の剰余類に分けて同じことをする。$\square$

後半の 2 彩色の各色は可測にならない。実際、この部分グラフを可測な色で塗るには 5 色以上が要る(Pay09 Theorem 1)。可測性を課すかどうかで彩色数が変わるグラフの例である。
次元を変えたときの簡単な評価を書く。

次元についての素朴な評価

$n\ge1$ について $n+1\le\chi(\mathbb{R}^n)\le(\lceil\sqrt n\rceil+1)^n$ である。

正単体と立方体

下界:1 辺 $1$ の正 $n$ 単体の $n+1$ 個の頂点は互いに距離 $1$ なので、すべて違う色を要する。
上界:$s:=1/\sqrt n$、$m:=\lceil\sqrt n\rceil+1$ とする。$a\in\mathbb{Z}^n$ について半開の立方体 $Q_a:=\prod_i[a_is,(a_i+1)s)$ を考えると、これらは $\mathbb{R}^n$ を分割する。$Q_a$ の点に色 $a\bmod m\in(\mathbb{Z}/m\mathbb{Z})^n$ を与える。同じ立方体の 2 点の距離は、各座標の差が $s$ 未満なので $\sqrt n\,s=1$ 未満である。$a\ne b$ で同じ色なら、ある $i$ で $b_i-a_i\ge m$(必要なら $a,b$ を入れ替える)で、$x\in Q_a$、$y\in Q_b$ について $y_i-x_i>(b_i-a_i-1)s\ge(m-1)s\ge\sqrt n\,s=1$ である。よって同じ色の 2 点の距離は $1$ でない。$\square$

$n=1$ では両辺が $2$ で、$\chi(\mathbb{R}^1)=2$ である。$n=2$ では $3\le\chi\le9$ で、単位距離グラフ の六角形と Moser スピンドルはこれを $4\le\chi\le7$ に改良している。上界の指数の底は Pro18 の $3+o(1)$ に遠く及ばない。$n=3$ の下界としては $\chi(\mathbb{R}^3)\ge6$ が知られている(CKR16 §1)。

上界の余裕

下界と上界の議論には性格の違いがある。単位距離グラフ の 7 彩色($d=\frac45$)の証明を読み直すと、同じ色の 2 点の距離は $\frac8{5\sqrt3}=0.923\ldots$ 以下か $\frac15(4\sqrt7-\frac8{\sqrt3})=1.192\ldots$ 以上である。つまりこの塗り分けは、距離 $1$ だけでなくその前後の区間の距離もまとめて避けている。一方、下界の配置は辺の長さがちょうど $1$ であることを使い、少しでも長さがずれると辺が消える。

反例の表

外す条件反例成り立たなくなること
点の集合が平面全体$\mathbb{Q}^2$(thm-hn-rational)2 色で足りるので、下界 $\chi\ge4$ は成り立たない
Euclid 距離$\mathbb{R}^2$ に 距離 $\max(\lvert x-x'\rvert,\lvert y-y'\rvert)$ を入れ、半開の単位正方形 $[a,a+1)\times[b,b+1)$ に色 $(a\bmod2,\ b\bmod2)$ を与える同じ正方形の 2 点の距離は $1$ 未満で、同じ色の別の正方形の 2 点の距離は $1$ より大きい。色数は $4$($(0,0),(1,0),(0,1),(1,1)$ は互いに距離 $1$)で、下界 $5$ は成り立たない
2 次元$\mathbb{R}^7$(prop-hn-dim)互いに距離 $1$ の 8 点があるので、上界 $7$ は成り立たない
thm-hn-compact の $k$ が共通頂点が可算無限個の完全グラフ有限部分グラフはどれも有限色で塗れるが、全体は有限色で塗れない

補足

似た名前の問題. Hadwiger予想 はグラフのマイナーと彩色数の問題で、別の問題である。
数え上げの問題との違い. 同じ単位距離グラフについて、辺の本数の最大値を問うのが Erdős の単位距離問題で(単位距離グラフ)、距離の種類の個数を問うのが Erdősの異なる距離問題 である。どちらも点の個数に対する増え方を問う問題で、色数の問題とは問い方が違う。
なぜ難しいか. prop-hn-h のように小さなグラフの彩色は手で分類できるが、見つかっている下界 $5$ のグラフは数百頂点以上ある。逆に少ない色の塗り分けを作ろうとすると、色が地図のような領域からなる場合には 5 色では足りない(Tow05)。

関連項目

参考文献

[2]
N. G. de Bruijn, P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations, Indagationes Mathematicae, 1951, pp. 371–373、Theorem 1
[3]
Geoffrey Exoo, Dan Ismailescu, The chromatic number of the plane is at least 5: a new proof, Discrete & Computational Geometry, 2020, pp. 216–226
[6]
K. J. Falconer, The realization of distances in measurable subsets covering R^n, Journal of Combinatorial Theory, Series A, 1981, pp. 184–189
[10]
Michael S. Payne, Unit distance graphs with ambiguous chromatic number, The Electronic Journal of Combinatorics, 2009, #N31、Theorem 1、§3
[11]
S. P. Townsend, Colouring the plane with no monochrome units, Geombinatorics, 2005, pp. 184–193

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する