四色定理

同義語：four color theoremfour colour theorem4色定理

概要

前提知識: グラフ, 平面グラフ, 彩色, 彩色数
四色定理は、平面上のどんな地図も、各国が 1 つながりの領域（飛び地をもたない）であれば、国境（点ではなく、長さのある境界線）を共有する国どうしが違う色になるように 4 色で塗り分けられるという定理である。1 点だけで接する国どうしは同じ色でもよい。たとえば、1 つの国のまわりを 5 つの国が輪のように囲み、輪の国どうしも隣とだけ国境を接している地図を考える。輪の 5 か国は奇数個なので、2 色で交互に塗ろうとすると最後の国で色がぶつかり、3 色が要る。中央の国は輪の 5 か国すべてと接するので、さらに 4 色目が要る。この地図は 4 色でちょうど塗れる（ex-four-color-theorem-wheel）。四色定理は、どんなに複雑な地図でも 5 色目が必要になることはない、と主張する。1852 年に Guthrie が問い、1976 年に Appel と Haken が計算機による膨大な場合の検証を用いて証明した（Die17 第 5 章の注、Wes01 §6.3）。証明は本記事の範囲を超えるので言明と出典を述べ、本記事では地図とグラフの対応、5 色なら初等的に証明できること（thm-four-color-theorem-five）、4 色の証明がどこで難しくなるか（prop-four-color-theorem-minimal）を扱う。

定義

本記事では、特に断らない限り、ループも平行辺ももたない有限の単純無向グラフを扱い、頂点彩色と彩色数は彩色数の記事の定義「頂点彩色の最小色数」に従う。平面グラフ、平面埋め込み、面は平面グラフの記事の定義「平面グラフ・平面埋め込み」「面」に従う。

地図とその塗り分け

平面を有限個の領域に分けたものを地図といい、各領域を国という。ここで各国は連結で、国の境界は有限個の弧からなるとする。2 つの国が正の長さをもつ境界の弧を共有するとき、2 つの国は 隣接する という。1 点だけを共有する国どうしは隣接しない。地図の各国に色を 1 つずつ割り当て、隣接する国どうしが異なる色になるようにすることを、地図の 塗り分け という。地図の国を頂点とし、隣接する国どうしを辺で結んだグラフを、地図の 隣接グラフ という。

地図の塗り分けは、隣接グラフの頂点彩色にほかならない。各国に 1 つずつ首都を置き、隣接する 2 国の首都を共有する境界を 1 回だけ横切る道で結べば、道どうしが交わらないように描けるので、隣接グラフは平面グラフである。逆に、任意の平面グラフはある地図の隣接グラフとして実現できる（どちらも Die17 §5.1。地図の外側の無限に広がる領域を海とみなし国に数えない流儀もあるが、結論は変わらない）。この対応により、地図についての主張は平面グラフについての次の主張と同値になる。

四色定理の主張

すべての平面グラフ $G$ について $\chi(G)\le4$ である。同値に、すべての地図は 4 色で塗り分けられる。

四色定理の証明と出典

この定理は Appel と Haken が 1976 年に発表し、AH77 とその続編で証明した。証明は計算機による膨大な場合の検証に依存し、人の手だけで全体を確かめることは現実的でない。Robertson・Sanders・Seymour・Thomas は同じ方針でより整理された証明を与え（RSST97）、Gonthier は証明全体を証明支援系 Coq で形式的に検証した（Gon08）。本記事はこの定理を証明せず、証明の構成を rem-four-color-theorem-structure で説明するにとどめる。

ループや平行辺を許すグラフで考える場合も、ループをもつグラフには頂点彩色がそもそも存在せず（彩色の記事の反例「ループを許す場合」）、平行辺は 1 本にまとめても彩色の条件が変わらないので、単純グラフの場合に帰着する。地図の隣接グラフにはループは現れない。

直感

平面グラフは「辺が少ない」グラフである。頂点が $n\ge3$ 個の単純平面グラフの辺は $3n-6$ 本以下であり（平面グラフの記事の系「単純平面グラフの辺数の上界」）、平均次数は $6$ より小さい。したがって、頂点をもつどの単純平面グラフにも次数が $5$ 以下の頂点がある（lem-four-color-theorem-degree-five）。そのような頂点 $v$ を除いたグラフを帰納法で塗り、最後に $v$ に色を与えるのが基本の方針である。$v$ の隣接頂点が使っている色が $4$ 色未満なら残りの色を $v$ に与えればよい。問題は隣接頂点がすでに全色を使っている場合で、このとき 2 色だけで塗られた部分（Kempe 鎖）の色を入れ替えて、隣接頂点から 1 色を追い出す（lem-four-color-theorem-kempe）。平面性はこの入れ替えがうまくいくことの保証に使われる。5 色ならこの議論で完結するが、4 色では次数 $5$ の頂点のところで 1 回の入れ替えでは足りなくなる。

例と反例

4 色が必要な平面グラフ

完全グラフ $K_4$ は平面グラフである（平面グラフの記事の例「完全グラフK4」）。どの 2 頂点も隣接するので $\chi(K_4)=4$ であり、四色定理の $4$ はこれより小さくできない。
5 頂点の閉路 $u_1u_2u_3u_4u_5$ に、すべての $u_i$ と隣接する頂点 $h$ を加えたグラフ $W$（車輪グラフ、車輪グラフ）は、$h$ を 5 角形の中心に置けば平面に描ける。閉路 $u_1\cdots u_5$ は奇閉路なので 3 色以上が要り（彩色の記事の反例「奇閉路の2-頂点彩色」）、$h$ はそのすべてと隣接するので $\chi(W)\ge4$ である。$u_1,\dots,u_5$ に色 $1,2,1,2,3$、$h$ に色 $4$ を与えれば 4 色で塗れるので $\chi(W)=4$ である。$W$ は $K_4$ を部分グラフとして含まない（$h$ 以外の 3 頂点が互いに隣接することはない）ので、4 色が必要になる理由は $K_4$ を含むことだけではない。冒頭の 1 国を 5 国が囲む地図の隣接グラフはこの $W$ である。

4 色より少なくて済む平面グラフ

木や偶数の長さの閉路は 2 色で、奇数の長さの閉路は 3 色で塗れる（彩色数の記事の例「基本的なグラフの彩色数」）。正八面体の頂点と辺からなるグラフは平面グラフで、向かい合う 2 頂点の組 3 つにそれぞれ 1 色を与えれば 3 色で塗れる（向かい合う 2 頂点は隣接しない）。四色定理は上界の主張であり、すべての平面グラフが 4 色を必要とするわけではない。

反例：平面グラフでないグラフ

完全グラフ $K_5$ は $\chi(K_5)=5$ である。$K_5$ は平面グラフでない（平面グラフの記事の命題「K5は平面グラフでない」）ので、四色定理と矛盾しない。満たさない仮定は平面性であり、平面性を外すと「$\chi(G)\le4$」は成り立たない。実際 $\chi(K_n)=n$ なので、一般のグラフの彩色数には上限がない。

反例：飛び地のある地図とトーラス上の地図

国が連結でない地図、すなわち飛び地をもつ国があり、飛び地も本国と同じ色で塗ることを求める場合には、4 色では塗り分けられない地図がある。たとえば 5 つの国が、飛び地を使えば互いにすべて隣接するように配置できる。このとき隣接関係は $K_5$ になり、5 色が要る（飛び地をもつ地図の塗り分けは Heawood が Hea1890 で論じた）。破る仮定は「各国が連結」であり、その結果、隣接グラフが平面グラフでなくなる。
トーラスの上の地図は 7 色で塗り分けられ、7 色が必要な地図もある。7 色で足りることは Heawood の上界（rem-four-color-theorem-surfaces）により、7 色が必要な地図があることは $K_7$ がトーラスに辺を交差させずに描けることによる（Hea1890、RY68）。四色定理は平面（あるいは球面）に固有の主張である。

性質

次数の小さい頂点

次数 5 以下の頂点の存在

頂点を 1 個以上もつ単純平面グラフ $G$ には、次数が $5$ 以下の頂点がある。

頂点数を $n$ とする。$n\le2$ なら各頂点の次数は $1$ 以下である。$n\ge3$ なら、平面グラフの記事の系「単純平面グラフの辺数の上界」により辺の数は $3n-6$ 以下である（この系は連結でない場合も含む）。握手補題により次数の総和は辺の数の 2 倍なので $6n-12$ 以下であり、$6n$ より小さい。すべての頂点の次数が $6$ 以上なら総和は $6n$ 以上になるので、次数 $5$ 以下の頂点がある。$\square$

Kempe 鎖

以下、平面グラフ $G$ の平面埋め込みを 1 つ固定する。頂点 $v$ に接続する辺は $v$ のまわりに巡回的な順序で並ぶ。$v$ の隣接頂点がこの順序で $w_1,\dots,w_d$ と並ぶとき、これを $v$ のまわりの 巡回順 という。
グラフ $H$ の頂点彩色 $c$ と相異なる 2 色 $\alpha,\beta$ について、色が $\alpha$ または $\beta$ である頂点全体が誘導する部分グラフの連結成分(グラフ)を、$c$ の $(\alpha,\beta)$ Kempe 鎖（Kempe鎖）という。1 つの Kempe 鎖の中で色 $\alpha$ と $\beta$ を入れ替えても頂点彩色のままである。実際、鎖の中の隣接頂点どうしは入れ替えの前後とも異なる色であり、鎖の頂点 $x$ と鎖の外の頂点 $y$ が隣接するなら、$y$ の色は $\alpha,\beta$ のどちらでもない（どちらかなら $y$ も同じ鎖に入る）ので、$x$ の新しい色 $\alpha$ または $\beta$ とも異なる。

Kempe 鎖による色の入れ替え

$G$ を平面埋め込みを固定した平面グラフ、$v$ を $G$ の頂点、$c$ を $G-v$（$v$ とそれに接続する辺を除いたグラフ）の頂点彩色とする。$v$ の隣接頂点 $a,a',b,b'$ が $v$ のまわりの巡回順でこの順に（間に他の隣接頂点を挟んでもよい）並び、$\alpha:=c(a)$、$\gamma:=c(a')$、$\beta:=c(b)$、$\delta:=c(b')$ は相異なり、$v$ の隣接頂点で色が $\alpha$ または $\beta$ のものは $a,b$ だけ、色が $\gamma$ または $\delta$ のものは $a',b'$ だけであるとする。このとき、$G-v$ の頂点彩色 $c'$ で、$v$ の隣接頂点に $c'$ が使う色の集合が、$c$ が使う色の集合から $\alpha$ または $\gamma$ を除いたものに等しいものが存在する。

$a$ を含む $c$ の $(\alpha,\beta)$ Kempe 鎖を $C$ とする。
$b\notin C$ の場合。$C$ の中で $\alpha$ と $\beta$ を入れ替えた彩色を $c'$ とする。上で見たように $c'$ は $G-v$ の頂点彩色である。$v$ の隣接頂点のうち $C$ に入りうるのは色が $\alpha,\beta$ の $a,b$ だけで、$b\notin C$ なので、色が変わるのは $a$ だけであり、$c'(a)=\beta$ となる。隣接頂点で色 $\alpha$ だったのは $a$ だけなので、$c'$ のもとで隣接頂点の色の集合から $\alpha$ だけが消え（$\beta$ は $b$ に残る）、他の色は変わらない。
$b\in C$ の場合。$C$ は連結なので、$G-v$ の中に $a$ から $b$ への道(グラフ) $P$ で、頂点の色がすべて $\alpha$ か $\beta$ であるものがある。$P$ に辺 $va$ と $vb$ を加えると $G$ の閉路 $Z$ が得られる。平面に描かれた $Z$ は閉曲線であり、Jordan曲線定理により平面から $Z$ を除いた部分はちょうど 2 つの領域（内部と外部）に分かれる（Die17 §4.1）。$v$ のまわりの巡回順で $a',b'$ は $a$ と $b$ に隔てられているので、辺 $va'$ と $vb'$ は $v$ から $Z$ の異なる側へ出ていく（平面埋め込みにおける頂点のまわりの局所的な様子による事実として証明せずに用いる。Die17 第 4 章）。$a',b'$ は $Z$ の頂点でない（色が $\gamma,\delta$ で、$v$ とも異なる）ので、辺 $va'$、$vb'$ は端点 $v$ 以外で $Z$ と交わらず、$a'$ と $b'$ は $Z$ の異なる側の領域にある。
ここで $a'$ を含む $c$ の $(\gamma,\delta)$ Kempe 鎖 $D$ に $b'$ が属したとすると、$G-v$ の中に $a'$ から $b'$ への道 $Q$ で、頂点の色がすべて $\gamma$ か $\delta$ であるものがある。$Q$ の頂点は色が $\alpha,\beta$ でなく $v$ でもないので $Z$ の頂点でなく、$Q$ の辺は $Z$ の辺と端点を共有しないので、平面埋め込みの定義により $Z$ と交わらない。すると $Q$ の描く曲線は $Z$ と交わらずに $a'$ と $b'$ を結び、$a'$ と $b'$ が $Z$ の異なる側にあることに反する。よって $b'\notin D$ である。$D$ の中で $\gamma$ と $\delta$ を入れ替えた彩色を $c'$ とすれば、前の場合と同じ理由で、隣接頂点の色の集合から $\gamma$ だけが消える。$\square$

5 色による塗り分け

平面グラフの 5 色彩色

すべての平面グラフ $G$ について $\chi(G)\le5$ である。

頂点数 $n$ についての数学的帰納法で示す。$n\le5$ なら各頂点に異なる色を与えればよい。$n\ge6$ とし、頂点数が $n$ より少ない平面グラフについて主張が成り立つとする。lem-four-color-theorem-degree-five により次数 $5$ 以下の頂点 $v$ がある。$G-v$ は平面埋め込みを制限すれば平面グラフなので、帰納法の仮定により色 $\{1,\dots,5\}$ の頂点彩色 $c$ をもつ。
$v$ の隣接頂点が使う色が 4 色以下なら、使われていない色を $v$ に与えれば $G$ の 5 色の頂点彩色になる。そうでなければ $v$ の次数は $5$ で、隣接頂点は相異なる 5 色をもつ。$v$ のまわりの巡回順を $w_1,\dots,w_5$ とし、lem-four-color-theorem-kempe を $a=w_1$、$a'=w_2$、$b=w_3$、$b'=w_4$ に適用する（隣接頂点の色は互いに異なるので補題の仮定を満たす）。得られる $c'$ のもとで隣接頂点の使う色は 4 色になるので、残る 1 色を $v$ に与えればよい。$\square$

この定理は五色定理と呼ばれ、Heawood が 1890 年に Kempe の議論を修正して証明した（Hea1890、Die17 §5.1）。$\chi(G)\le6$ であれば、lem-four-color-theorem-degree-five だけで Kempe 鎖を使わずに示せる（彩色数の記事の系「平面グラフの 6 色彩色」）。

4 色の場合に残る困難

同じ議論を 4 色で行うと、次数 $4$ 以下の頂点は処理できる。

最小反例の次数

4 色で塗れない平面グラフが存在すると仮定し、そのうち頂点数が最小のものを $G$ とする。このとき $G$ のすべての頂点の次数は $5$ 以上であり、$G$ には次数がちょうど $5$ の頂点がある。

次数 $4$ 以下の頂点 $v$ があったとする。頂点数の最小性により、平面グラフ $G-v$ は色 $\{1,2,3,4\}$ の頂点彩色 $c$ をもつ。$v$ の隣接頂点の使う色が 3 色以下なら、残る色を $v$ に与えて $G$ が 4 色で塗れ、矛盾する。そうでなければ $v$ の次数は $4$ で、隣接頂点は相異なる 4 色をもつ。$v$ のまわりの巡回順を $w_1,\dots,w_4$ とし、lem-four-color-theorem-kempe を $a=w_1$、$a'=w_2$、$b=w_3$、$b'=w_4$ に適用すると、隣接頂点の使う色が 3 色になる彩色 $c'$ が得られ、残る色を $v$ に与えて矛盾する。よってすべての頂点の次数は $5$ 以上であり、lem-four-color-theorem-degree-five と合わせて次数ちょうど $5$ の頂点がある。$\square$

Kempe の議論が破綻する点

Kempe は 1879 年に、次数 $5$ の頂点についても Kempe 鎖の入れ替えで 4 色の場合を処理できると主張したが、Heawood がその議論の誤りを指摘した（Hea1890）。次数 $5$ の頂点の隣接頂点 $w_1,\dots,w_5$ が 4 色を使うとき、ある色が 2 回現れる（たとえば $w_2$ と $w_5$ がともに色 $2$ で、$w_1,w_3,w_4$ が色 $1,3,4$）。このとき lem-four-color-theorem-kempe の「色 $\alpha,\beta$ をもつ隣接頂点は $a,b$ だけ」という仮定が満たされず、色 $2$ を追い出すには 2 本の Kempe 鎖を入れ替える必要がある。Kempe は 2 つの入れ替えを続けて行ったが、1 つ目の入れ替えで 2 つ目の鎖の形が変わりうることを見落としていた。この議論の詳細は Wes01 §6.3 にある。

証明の構成

回避不可能な集合と可約な配置

Appel–Haken と RSST97 の証明は、prop-four-color-theorem-minimal の考え方を大きく押し広げたものである。最小反例 $G$ は、辺を加えて面がすべて三角形の平面グラフ（三角形分割）にしてよい（辺を加えても平面性は保たれ、4 色で塗れないことも保たれる）。証明は次の 2 段からなる。

回避不可能性：有限個の「配置」（頂点の次数の情報を付けた小さな部分グラフ）の集合 $\mathcal U$ を用意し、最小次数 $5$ 以上の三角形分割は必ず $\mathcal U$ のどれかを含むことを示す。これは、各頂点に $6-\deg v$ の「電荷」を置く（平面グラフの記事の定理「Eulerの公式」から総電荷は正の $12$ になる）と、電荷を決まった規則で隣へ移しても総和は変わらないので、どこかに正の電荷が残る、という 放電法（放電法）で示す。
可約性：$\mathcal U$ の各配置について、それを含むグラフが最小反例になりえないことを、配置のまわりの 4 色彩色をすべて調べ、Kempe 鎖の入れ替えを含む操作で内部まで延ばせることを確かめて示す。prop-four-color-theorem-minimal の次数 $4$ 以下の頂点の処理は、この可約性の最も簡単な場合である。
2 つを合わせると最小反例は存在しない。Appel–Haken の証明では千を超える配置の可約性を計算機で確かめた。RSST97 は 633 個の配置と 32 個の放電規則による証明を与え、同じ方法で $n$ 頂点の平面グラフを 4 色で塗る $O(n^2)$ 時間の算法を与えた。計算機による検証を本質的に含む証明であることは当時大きな議論を呼んだが、Gon08 の形式的検証により、少なくとも証明の論理的な正しさについての疑いは大きく減った。

計算量と他の曲面

3 色で塗れるかの判定

四色定理により、平面グラフが 4 色で塗れるかどうかを判定する問題は自明（つねに塗れる）である。一方、平面グラフが 3 色で塗れるかどうかを判定する問題は NP完全である（GJS76）。したがって、4 色の塗り分けは多項式時間で求められる（rem-four-color-theorem-structure）が、3 色で足りるかどうかを効率よく判定する方法は、P と NP が一致しない限り存在しない。

曲面上の地図の塗り分け

種数 $g\ge1$ の向き付け可能な閉曲面の上に辺を交差させずに描けるグラフ $G$ について、Heawood は
$$ \chi(G)\le\left\lfloor\frac{7+\sqrt{1+48g}}{2}\right\rfloor $$
を示した（Hea1890）。Ringel と Youngs は、$g\ge1$ ではこの上界に等しい彩色数をもつグラフがその曲面に描けることを示した（RY68）。右辺は $g=0$ で $4$ になるが、Heawood の証明は $g\ge1$ の場合のものであり、$g=0$ の場合の上界 $4$ はちょうど四色定理にあたる。$g=1$（トーラス）では右辺は $7$ である（ex-four-color-theorem-other-maps の 2）。

補足

役割分担：彩色数の一般的な性質（上界と下界、貪欲彩色、Brooks の定理）は彩色数、頂点彩色と辺彩色の定義は彩色、平面グラフの辺数の評価と Euler の公式は平面グラフの記事にある。本記事は平面グラフの彩色の上界（4 色と 5 色）を扱う。
文献：五色定理と四色定理の解説は Die17 §5.1 と Wes01 §6.3 にある。