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$ 色で足りる。
前提知識: 単位距離グラフ, 彩色数, 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 年 9 月のプレプリント Ope26 は、色の集合に条件を付けない 5 彩色が存在しないこと、すなわち $\chi(\mathbb{R}^2)\ge6$ を主張している。参考文献に挙げた公開の文書は、この主張の Lean による形式化を報告している。可測な条件への還元と幾何の議論からなるもので、計算機で有限グラフを探す従来の方法とは別の道である。Blo26 問題 508(2026 年 10 月 16 日更新)は、これを受けて最良の評価を $6\le\chi\le7$ と記載している。Ope26 は 2026 年 11 月の時点でプレプリントの段階にあるので、この記事は到達点に含めない。主張が正しい場合でも、値が $6$ か $7$ かを決める問題は残る。
単位距離グラフ では Moser スピンドルの彩色数から下界 $4$ を出した。同じ下界を、グラフを先に書かずに平面の上で直接示せる。
$c$ を平面の 3 彩色とする。$\lvert x-y\rvert=\sqrt3$ なら $c(x)=c(y)$ である。
線分 $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$
$\chi(\mathbb{R}^2)\ge4$ である。
3 彩色 $c$ があるとする。点 $x$ を固定すると、lem-hn-rhombus により $x$ を中心とする半径 $\sqrt3$ の円の上の点はすべて $x$ と同じ色である。この円には長さ $1$ の弦があるので、距離 $1$ の同色の 2 点が見つかる。矛盾である。$\square$
この証明で実際に使った点は有限個である。弦の両端を $p,q$ とし、$x$ と $p$、$x$ と $q$ のそれぞれにひし形を置くと 7 頂点 11 辺のグラフができる。これが Moser スピンドルである。
もう 1 つの小さな例は構成が違う。
原点 $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 本である。
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$
$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$ 以上の有限グラフの証拠がある。ただし、下界を示すのにそのグラフを実際に書き出す必要はない。
de Grey の構成(dG18)の出発点は、中心と 1 辺 $1$ の正六角形の頂点からなる 7 頂点 12 辺のグラフ $H$ である。外周の 1 つおきの 3 頂点は 1 辺 $\sqrt3$ の正三角形をなす。これらが同じ色のとき 単色の三つ組 という。
回転・鏡映・色の入れ替えを除いて、$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$ のような無理数を座標にもつ。これは偶然ではない。
$\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)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する