四色定理：地図が4色で塗れる理由と、コンピュータが書いた最初の証明

0. この記事の要点

地図帳の塗り絵をするとき、隣り合う国を違う色にしようとすると、不思議なことにいつも 4 色あれば足ります。本当にどんな地図でもそうなのか、そうだとして理由は何なのか、という素朴な疑問がこの記事の出発点です。読み終えると、4 色の手前の 6 色・5 色までは自分の手で証明できるようになり、最後の 4 色だけがなぜ人間の手に負えなかったのかも分かります。

• 平面に描かれたどんな地図も、隣り合う国が異なる色になるように 4 色で塗り分けられます。これが四色定理です。
• 「地図」を「平面グラフ」（点と線で描いた図で、線が途中で交わらないもの）に翻訳すると、問題は「平面グラフの頂点を 4 色で塗れるか」という、絵ではなく点と線の問題になります。
• オイラーの公式から「平面グラフには次数 5 以下の頂点が必ずある」が導かれ、そこから六色定理はほとんど自動的に、五色定理は「ケンペ鎖」という道具で証明できます。ここまでは紙と鉛筆で 1 時間の仕事です。
• ところが 5 から 4 への最後の一歩だけが異様に硬い。1976 年、Appel と Haken が約 1900 個の「配置」をコンピュータで検査してようやく決着しました。人間が全証明を読み切れない最初の主要定理です。
• 1997 年に証明は大幅に簡略化され、2005 年には証明支援系 Coq（証明の各ステップをソフトウェアが機械的に検査する仕組み）で完全に形式化されました。「コンピュータの証明を信じてよいか」という問いは、いまや「どのソフトウェアをどこまで信じるか」という、より具体的な問いに姿を変えています。

この記事で使う事前知識

• グラフの頂点・辺・次数: 点（頂点）とそれを結ぶ線（辺）の図で、頂点に接する辺の本数がその頂点の次数です。→ 次数と一筆書き
• 平面グラフ: 辺が途中で交わらないように平面に描けるグラフのことです。→ 平面グラフ
• 双対グラフ: 地図の各国に点を打ち、隣り合う国の点どうしを線で結んでできるグラフのことです。→ 双対グラフ
• 連結成分: グラフを線をたどって行き来できるかたまりに分けたときの、1 つ 1 つのかたまりのことです。

1. 動機：地図帳の塗り絵から始まった問題

1852 年、ロンドンの学生フランシス・ガスリー（Francis Guthrie）はイングランドの州の地図に色を塗っていて、あることに気づきました。隣り合う州を違う色にしたいのですが、どう工夫しても 4 色あれば足りてしまう。5 色目を使わざるをえない地図を作ろうとしても、なぜか作れない。

彼は弟のフレデリック（当時、数学者ド・モルガンの学生でした）にこの疑問を伝え、フレデリックは指導教員のド・モルガンに尋ねました。ド・モルガンは同年 10 月 23 日、ハミルトンに宛てた手紙でこの問題を紹介しています。四色問題の記録された誕生日です。

問いは子どもでも理解できます。

平面上の地図が与えられたとき、国境を共有する 2 国が必ず異なる色になるように塗り分けるには、何色あれば十分か。

「十分」の側は 4 色というのが答えです。「必要」の側、つまり 4 色ないと足りない地図があることは、すぐ後の 例 2.3 で確かめます。つまり答えはぴったり 4 です。

ここで注意してほしいのは、この問題の難しさがどこにも見えないことです。問題文には微分も無限も出てきません。にもかかわらず、解決までに 124 年かかり、その解決方法は数学界にちょっとした騒動を起こしました。単純な問いが恐ろしく深い、という点で、この問題は コラッツ予想、とくに コラッツ写像（定義 2.1）［コラッツ予想］ のように定義が数行で終わる問題と同じ種族に属します。

ノート

「なぜ 4 なのか」に、直感的で短い理由は今のところ知られていません。後で見るように 6 色や 5 色なら理由はきれいに説明できます。最後の 1 色分だけが、なぜか説明を拒み続けています。

2. 準備：地図をグラフに翻訳する

2.1. 地図とは何か

まず「地図」を数学の言葉で固定します。ここを曖昧にすると定理が偽になってしまうので、丁寧にやります。

定義 2.1（地図と塗り分け）↗

平面を有限個の領域 $R_1, \ldots, R_n$（国）に分割したものを地図と呼びます。ただし各国 $R_i$ は連結な開集合とし、境界は有限本の曲線からなるものとします。2 つの国 $R_i, R_j$ が隣接するとは、両者の境界が共有部分をもち、しかもその共有部分が 1 点ではなく曲線を含むことをいいます。

写像 $c \colon \{R_1,\ldots,R_n\} \to \{1,\ldots,k\}$ が**$k$ 彩色**であるとは、隣接するどの 2 国 $R_i, R_j$ についても $c(R_i) \neq c(R_j)$ が成り立つことをいいます。

2 つの条件が効いています。

（a）国は連結。飛び地を認めると定理は壊れます（例 2.4）。

（b）1 点で接するだけでは隣接としない。円グラフのように中心で多数の国が集まる図を考えれば分かります。1 点で接するだけの国どうしを「隣接」と数えると、扇形を $n$ 枚並べた円だけで $n$ 色必要になり、これも定理を壊します。「国境」とは線であって点ではない、という常識をそのまま採用しているわけです。

2.2. 双対グラフ

地図のままでは扱いにくいので、点と線に翻訳します。各国の内部に「首都」を 1 つ打ち、隣接する 2 国の首都を国境をまたぐ線でつなぎます。こうしてできる図形を双対グラフと呼びます。

地図（左）とその双対グラフ（右）。中央の小国 D は A, B, C のすべてと接し、A, B, C も互いに接するので、双対グラフは 4 頂点がすべてつながった K4 になります。

大事なのは、この双対グラフが平面に描けることです。つないだ線は国境を 1 回ずつまたぐだけなので、互いに交わらないように描けます。これで問題が完全に翻訳されました。

定義 2.2（平面グラフとその彩色）↗

グラフ $G = (V, E)$ は、頂点の有限集合 $V$ と、頂点の 2 元部分集合からなる辺の集合 $E$ の組です。この記事のグラフはすべて単純、すなわち自己ループも多重辺もないものとします。頂点 $v$ に接する辺の本数を $v$ の次数といい $\deg(v)$ と書きます。

$G$ が平面グラフであるとは、頂点を平面上の相異なる点に、辺を端点を結ぶ曲線に対応させて、辺どうしが端点以外で交わらないように描けることをいいます。そのような描き方を 1 つ固定したものを平面描画と呼びます。

写像 $c \colon V \to \{1,\ldots,k\}$ が $G$ の**$k$ 彩色であるとは、辺 $\{u,v\} \in E$ をもつどの 2 頂点についても $c(u) \neq c(v)$ が成り立つことをいいます。$k$ 彩色が存在する最小の $k$ を $G$ の彩色数** $\chi(G)$ といいます。

次数と平面グラフの基本は 次数と一筆書き（定義 5.1）［オイラーとラマヌジャン］ および 平面グラフ（定義 5.4）［オイラーとラマヌジャン］ でも導入しています。

以下、地図の話はすべてこの言葉に置き換えて進めます。示したいのは「$G$ が平面グラフなら $\chi(G) \le 4$」です。

例 2.3（4 色が必要な地図が実在する）

上の図の地図をそのまま使います。国 A, B, C は円環状に並んで互いに隣接し、中央の国 D は A, B, C のすべてと隣接しています。したがって双対グラフでは 4 頂点のどの 2 つも辺で結ばれています（これを $K_4$ と書きます）。

3 色で塗れたと仮定しましょう。$c(A), c(B), c(C)$ は互いに隣接するので 3 つとも異なり、$\{1,2,3\}$ をちょうど使い切ります。$D$ はこの 3 国すべてと隣接するので $c(D)$ は $1,2,3$ のどれとも異なる値でなければならず、$\{1,2,3\}$ の中に候補が残りません。矛盾です。よって $\chi(K_4) = 4$ で、この地図には 4 色が要ります。

「4 色で十分」の方が定理、「4 色が必要」の方はこの一例で終わりです。難しいのは常に「十分」側です。

例 2.4（飛び地を認めると、必要な色数はいくらでも増える）

定義 2.1 の条件（a）を外すとどうなるかを見ます。$n$ 個の国 $C_1, \ldots, C_n$ を用意し、それぞれに「本土」1 片と「飛び地」$n-1$ 片を与えます。上段に縦長の長方形（本土）$C_1, C_2, \ldots, C_n$ を左から並べ、その下端に沿って横一線の国境を引きます。

下段では、本土 $C_j$ の真下の区画を横に $n-1$ 個の小さな長方形へ区切り、$i \ne j$ なる各国 $C_i$ の飛び地を 1 つずつ置きます。すると $C_i$ は、$j \ne i$ なるどの本土 $C_j$ とも、その真下に置いた自分の飛び地を通じて国境線を共有します。$i \ne j$ なるすべての組 $(C_i, C_j)$ が隣接するので、$n$ 色が必要です。$n = 100$ とすれば 100 色要ります。

四色定理が「国は連結」という一見どうでもいい条件に完全に依存していることが分かります。飛び地をもつ国を含む現実の地図（たとえばロシアのカリーニングラード州を含む世界地図）に、この定理はそのままでは適用できません。

3. まず六色定理を証明する

いきなり 4 は無理なので、6 から始めます。ここで使う道具はオイラーの公式（オイラーの多面体定理（定理 5.5）［オイラーとラマヌジャン］）ただ 1 つです。

命題 3.1（オイラーの多面体公式）✓

連結な平面グラフの平面描画において、頂点数を $V$、辺数を $E$、その描画が平面を分ける領域（面、外側の非有界領域も 1 つと数える）の個数を $F$ とすると、

$$V - E + F = 2$$

が成り立ちます。

証明（命題 3.1）

辺数 $E$ についての帰納法で示します。

基底：$E = 0$ のとき。連結なので頂点は 1 個だけ、面は平面全体の 1 つです。$V - E + F = 1 - 0 + 1 = 2$ で成立します。

帰納段階：$E \ge 1$ とし、辺数が $E - 1$ 以下の連結平面描画では公式が成り立つと仮定します。2 つの場合に分けます。

(i) $G$ が閉路を含む場合。 その閉路上の辺 $e$ を 1 本取ります。$e$ は閉路上にあるので、$e$ を取り除いても連結性は保たれます。またジョルダンの曲線定理により、閉路は平面を内側と外側に分けているので、$e$ の両側は相異なる 2 つの面です。$e$ を消すとこの 2 面が合体して 1 面になります。よって $V' = V,\ E' = E-1,\ F' = F-1$ となり、帰納法の仮定から $V' - E' + F' = 2$、すなわち $V - (E-1) + (F-1) = 2$ で、これは $V - E + F = 2$ と同値です。

(ii) $G$ が閉路を含まない場合。 連結かつ閉路なしなので $G$ は木です。木には次数 1 の頂点（葉）が存在します。葉 $v$ とそれに接する辺 $e$ を取り除くと、残りも連結な木です。$e$ の両側は同じ面なので面の数は変わりません。よって $V' = V-1,\ E' = E-1,\ F' = F$ で、帰納法の仮定から $(V-1) - (E-1) + F = 2$、すなわち $V - E + F = 2$ です。

どちらの場合も公式が従います。

∎

例 3.2（立方体で確かめる）

立方体の 8 個の頂点と 12 本の辺からなるグラフを考えます。立方体を 1 つの面から覗き込むように平面に潰すと、大きな正方形の中に小さな正方形が入り、対応する角どうしが結ばれた図になります。これは辺が交わらない描き方なので平面描画です。

面を数えると、大きな正方形と小さな正方形の間にできる 4 つの台形、内側の小正方形、そして図全体の外側で、$4 + 1 + 1 = 6$ 個です。確かに

$$V - E + F = 8 - 12 + 6 = 2$$

となり、命題 3.1 が成り立っています。立体としての立方体の面が 6 枚であることと一致しているのも、平面に潰したとき「もとの手前の面」が外側の無限領域に化けたからです。

オイラーの公式から、平面グラフは「辺を持ちすぎられない」という制限が出ます。これが以降のすべての鍵です。

補題 3.3（平面グラフの辺数の上界）✓

$G$ を頂点数 $V \ge 3$ の単純平面グラフとすると、辺数 $E$ について

$$E \le 3V - 6$$

が成り立ちます。

証明（補題 3.3）

まず $G$ が連結な場合を示します。$G$ の平面描画を 1 つ固定し、面の個数を $F$ とします。

各面について、その境界を一周する閉じた歩道（境界歩道）の長さを考えます。$G$ は単純で $V \ge 3$ かつ連結なので、どの面の境界歩道も長さ 3 以上です。実際、長さ 1 は自己ループ、長さ 2 は多重辺を必要としますが、単純グラフにはどちらもありません。長さ 2 になりうるのは 1 本の辺を往復する場合ですが、それは $V = 2$ で辺が 1 本しかないときに限られ、$V \ge 3$ かつ連結という仮定に反します。

一方、各辺はちょうど 2 回だけ境界歩道に現れます（両側の面が異なるときは各面で 1 回ずつ、同じ面のときはその面で 2 回）。すべての面について境界歩道の長さを足すと、辺の登場回数の総和 $2E$ に等しくなります。したがって

$$2E = \sum_{f} (\text{面 } f \text{ の境界歩道の長さ}) \ge 3F$$

すなわち $F \le \frac{2}{3}E$ です。これを 命題 3.1 の $F = 2 - V + E$ に代入すると

$$2 - V + E \le \tfrac{2}{3}E$$

となり、両辺から $\frac{2}{3}E$ を引いて整理すると $\frac{1}{3}E \le V - 2$、すなわち $E \le 3V - 6$ を得ます。

$G$ が連結でない場合は、平面描画を保ったまま異なる連結成分の間に辺を追加して連結にできます（成分どうしは平面上で分離しているので、外側の面を通る辺を引けます）。辺を足しても平面性と単純性は保てるので、得られた連結グラフ $G'$ に上の結果を適用して $E \le E(G') \le 3V - 6$ となります。

∎

系 3.4（小さい次数の頂点の存在）✓

$G$ を単純平面グラフとすると、$G$ には次数 5 以下の頂点が少なくとも 1 つ存在します。

証明（系 3.4）

頂点数を $V$ とします。$V \le 6$ のときは、単純グラフの次数は $V - 1 \le 5$ 以下なので主張は自明に成り立ちます。以下 $V \ge 7$（特に $V \ge 3$）とします。

すべての頂点の次数が 6 以上であると仮定します。握手補題（各辺は 2 つの頂点の次数に 1 ずつ寄与する）より

$$2E = \sum_{v} \deg(v) \ge 6V$$

なので $E \ge 3V$ です。ところが 補題 3.3 より $E \le 3V - 6$ でしたから、$3V \le E \le 3V - 6$ となり $0 \le -6$ という矛盾が生じます。よって次数 5 以下の頂点が存在します。

∎

定理 3.5（六色定理）✓

すべての単純平面グラフ $G$ について $\chi(G) \le 6$ が成り立ちます。すなわち、平面上のどんな地図も 6 色で塗り分けられます。

証明（定理 3.5）

頂点数 $V$ についての帰納法で示します。

基底：$V \le 6$ のとき、すべての頂点に別々の色を割り当てれば 6 色で足ります。

帰納段階：$V \ge 7$ とし、頂点数が $V-1$ 以下のすべての単純平面グラフが 6 彩色をもつと仮定します。系 3.4 により $\deg(v) \le 5$ となる頂点 $v$ が取れます。$v$ とそれに接する辺をすべて取り除いたグラフを $G - v$ とすると、これは頂点数 $V-1$ の単純平面グラフです（部分グラフは平面グラフです）。帰納法の仮定より $G - v$ は 6 彩色 $c$ をもちます。

$v$ の隣接頂点は高々 5 個なので、それらが使っている色は高々 5 種類です。6 色のうち少なくとも 1 色は $v$ の隣にありません。その色を $c(v)$ とすれば、$v$ に接するすべての辺で色が異なり、$G$ 全体の 6 彩色が得られます。

∎

証明を振り返ると、効いているのは「次数 5 以下の頂点が必ずある」という一点だけです。この頂点を取り除いて小さくし、戻すときに色が 1 つ余っていればよい。次数 5 以下の頂点に対して色を 6 個用意しておけば、必ず 1 個余ります。実に安上がりな議論です。

4. ケンペ鎖と五色定理

6 色は簡単すぎました。5 色にすると、上の議論はちょうど 1 箇所で破綻します。次数 5 の頂点を消して戻すとき、5 人の隣人が 5 色を使い切っていると、余る色がないのです。

ここで登場するのが、1879 年に Alfred Bray Kempe が導入した道具です。彼はこの道具で四色定理を「証明」し、11 年間それは正しいと信じられました。1890 年、Percy John Heawood が誤りを見つけますが、同時に「この議論は 5 色なら通る」ことを示しました。壊れた証明から本物の定理が 1 つ救い出されたわけです。

定義 4.1（ケンペ鎖）↗

$G$ の彩色 $c$ と、2 つの色 $i, j$ が与えられたとします。色が $i$ または $j$ である頂点全体が誘導する部分グラフを $H_{i,j}$ と書きます。$H_{i,j}$ の各連結成分を、$c$ に関する $(i,j)$-ケンペ鎖と呼びます。

ケンペ鎖が道具として役に立つのは、次の性質があるからです。彩色を「局所的に組み替える」ことが許されるので、都合の悪い色の配置を都合のよいものに直せます。

補題 4.2（ケンペ鎖の入れ替え）✓

$c$ を単純グラフ $G$ の彩色、$K$ を $c$ に関する $(i,j)$-ケンペ鎖とします。$K$ に属する頂点についてのみ色 $i$ と色 $j$ を入れ替え、$K$ に属さない頂点の色はそのままにして得られる写像 $c'$ は、ふたたび $G$ の彩色です。

証明（補題 4.2）

辺 $\{u,w\} \in E$ を任意に取り、$c'(u) \ne c'(w)$ を確かめます。$u, w$ が $K$ に属するかどうかで 3 通りに分かれます。

(1) $u, w$ がともに $K$ の中にある場合。 $c(u) \ne c(w)$ で、どちらも色は $i$ か $j$ ですから、$\{c(u), c(w)\} = \{i, j\}$ です。入れ替えると $c'(u), c'(w)$ も $i$ と $j$ を 1 つずつ取るので異なります。

(2) $u, w$ がともに $K$ の外にある場合。 どちらの色も変わらないので $c'(u) = c(u) \ne c(w) = c'(w)$ です。

(3) $u \in K$、$w \notin K$ の場合。 $u$ の色は $i$ か $j$ です。もし $w$ の色も $i$ か $j$ なら、$w$ は $H_{i,j}$ の頂点で、しかも $u$ と辺で結ばれているので $u$ と同じ連結成分、つまり $K$ に属してしまい仮定に反します。よって $c(w)$ は $i$ でも $j$ でもありません。$c'(u)$ は $i$ か $j$ ですから $c'(u) \ne c(w) = c'(w)$ です。

以上ですべての辺で色が異なり、$c'$ は彩色です。

∎

次の五色定理の証明の方針は、六色定理と同じく「次数 5 以下の頂点 $v$ を取り除き、残りを塗ってから戻す」ことです。困るのは $v$ のまわりの 5 人の隣人が 5 色を使い切っている場合だけで、そのときはケンペ鎖で色を 1 つ空けます。空けられない場合（場合 2）が閉曲線の議論になります。状況は次の図のようになっています。

場合 2 の状況（模式図）。v の隣人 v1〜v5 が v のまわりをこの順に並びます。v1 から v3 へ色 1 と 3 だけを通る道 P があると、P と辺 v-v1、v3-v が閉曲線をつくります。v2 はその内側、v4 と v5 は外側にあり、内側の頂点から外側の頂点へは、色 1 と 3 の頂点を通らずには出られません。

定理 4.3（五色定理）✓

すべての単純平面グラフ $G$ について $\chi(G) \le 5$ が成り立ちます。

証明（定理 4.3）

頂点数 $V$ についての帰納法で示します。$V \le 5$ なら全頂点に別の色を与えれば済みます。以下 $V \ge 6$ とし、頂点数 $V-1$ 以下では 5 彩色が存在すると仮定します。

系 3.4 により $\deg(v) \le 5$ なる頂点 $v$ を取り、$G$ の平面描画を 1 つ固定します。$G - v$ は頂点数 $V-1$ の単純平面グラフなので、帰納法の仮定より 5 彩色 $c$ をもちます。

$v$ の隣接頂点が使う色が 4 種類以下なら、余った色を $c(v)$ とすれば終わりです（$\deg(v) \le 4$ の場合も自動的にここに含まれます）。よって残るのは、$\deg(v) = 5$ で、5 個の隣接頂点が 5 色をすべて使っている場合だけです。

平面描画において $v$ から出る 5 本の辺を、$v$ のまわりを回る順に並べ、その先の頂点を順に $v_1, v_2, v_3, v_4, v_5$ とします。色の名前を付け替えて $c(v_k) = k$（$k = 1,\ldots,5$）としてよいとします。

場合 1：$v_1$ と $v_3$ が $H_{1,3}$ の異なる連結成分にある。 $v_1$ を含むケンペ鎖の中だけで色 1 と 3 を入れ替えます。補題 4.2 よりこれは $G-v$ の 5 彩色のままです。$v_3$ はこの鎖に入っていないので色 3 のままであり、$v_1$ の色は 3 に変わりました。よって $v$ の隣接頂点の色は $3, 2, 3, 4, 5$ となり、色 1 がどこにも現れません。$c(v) = 1$ とおけば $G$ の 5 彩色が完成します。

場合 2：$v_1$ と $v_3$ が $H_{1,3}$ の同じ連結成分にある。 このとき $v_1$ から $v_3$ へ、色が 1 と 3 の頂点だけを通る道 $P$ が存在します。この $P$ に、辺 $v v_1$ と辺 $v_3 v$ を付け加えると、平面描画の中の閉曲線 $C$ ができます。

ジョルダンの曲線定理により、$C$ は平面を内部と外部に分けます。$v$ のまわりの巡回順序が $v_1, v_2, v_3, v_4, v_5$ であることから、$v_2$ は $C$ の一方の側に、$v_4$ は他方の側にあります（$v_2$ は $v_1$ と $v_3$ に挟まれた区画に、$v_4$ は $v_3$ と $v_1$ を反対回りに結ぶ区画にあるためです）。

さて $v_2$ と $v_4$ が $H_{2,4}$ の同じ連結成分にあったとしましょう。すると $v_2$ から $v_4$ へ、色 2 と 4 の頂点だけを通る道 $Q$ が存在します。$Q$ は $C$ の内側から外側へ渡るので、平面描画では $C$ と交わらざるをえません。しかし辺どうしは端点以外で交わらないので、交わりは共有頂点でなければなりません。$C$ 上の頂点は $v$ と、色が 1 か 3 の頂点だけです。$Q$ 上の頂点の色は 2 か 4 なので色は一致せず、また $v$ は $G - v$ に属さないので $Q$ 上にありません。交わりようがなく、矛盾です。

したがって $v_2$ と $v_4$ は $H_{2,4}$ の異なる成分にあります。$v_2$ を含むケンペ鎖で色 2 と 4 を入れ替えると、$v_2$ の色が 4 に変わり $v_4$ は 4 のまま。$v$ の隣接頂点の色は $1, 4, 3, 4, 5$ となって色 2 が空きます。$c(v) = 2$ として $G$ の 5 彩色を得ます。

いずれの場合も 5 彩色が構成でき、帰納法が完成します。

∎

注意 4.4（ケンペはどこで間違えたか）

Kempe は 1879 年、同じ枠組みで 4 色を主張しました。4 色の場合、$\deg(v) = 5$ の頂点を消すと隣人 5 人に色は 4 つしかないので、必ずどこかで色が重複します。重複を利用して場合分けすると、最後に「2 本のケンペ鎖を同時に入れ替える」必要のある状況が残ります。Kempe はこれを問題なくできると考えました。

しかし 2 つの鎖が絡み合っていると、一方の入れ替えがもう一方の鎖の形を変えてしまい、2 回目の入れ替えがもはや正当でなくなることがあります。Heawood は 1890 年、まさにそれが起きる 25 国の地図を作って示しました。上の 定理 4.3 の証明で入れ替えを1 回しか行っていないのは偶然ではありません。1 回で済むのが 5 色、2 回必要になるのが 4 色で、その差が 86 年分の難しさでした。

例 4.5（「端から順に塗る」では 4 色に届かない）

「小さい次数の頂点から順に塗ればいい」という素朴な戦略（貪欲彩色）がどれくらい当てにならないかを見ておきます。

6 頂点 $a_1, a_2, a_3, b_1, b_2, b_3$ を取り、$a_i$ と $b_j$ を $i \ne j$ のときだけ辺で結びます。この 6 頂点 6 辺のグラフは $a_1 b_2 a_3 b_1 a_2 b_3 a_1$ という長さ 6 の閉路で、平面に描けます。$a$ 側と $b$ 側で塗り分ければ 2 色で足ります。

ところが頂点を $a_1, b_1, a_2, b_2, a_3, b_3$ の順に並べ、「まだ使われていない最小の色」を順に割り当てると次のようになります。

順番	頂点	すでに塗られた隣人	与えられる色
1	$a_1$	なし	1
2	$b_1$	なし（$b_1$ の隣は $a_2, a_3$）	1
3	$a_2$	$b_1$（色 1）	2
4	$b_2$	$a_1$（色 1）	2
5	$a_3$	$b_1$（1）, $b_2$（2）	3
6	$b_3$	$a_1$（1）, $a_2$（2）	3

2 色で足りるグラフに 3 色を使ってしまいました。同じ構成を $n$ 組に拡張すると貪欲法は $n$ 色を使います。彩色は「順番に塗る」だけでは制御できません。

5. 5 から 4 へ：不可避集合と可約配置

定理 5.1（四色定理）※

すべての単純平面グラフ $G$ について $\chi(G) \le 4$ が成り立ちます。同値に、定義 2.1 の意味のどんな地図も 4 色で塗り分けられます。

注意 5.2（この定理の証明について）

証明は Appel と Haken（1976 年、Koch の協力による計算部分を含む）によって与えられ、1997 年に Robertson, Sanders, Seymour, Thomas によって大幅に簡略化されました。いずれもコンピュータによる有限個の場合の検査を含み、本記事に収まる長さではありません。以下の §5.1 以降と §6 で証明の骨格と、その性格について述べます。完全な議論は参考文献の Robertson–Sanders–Seymour–Thomas (1997)、形式化については Gonthier (2008) を参照してください。

5.1. 証明の骨格

証明の枠組み自体は 19 世紀から変わっていません。最小反例を取って、それが存在しえないことを示します。

四色定理の証明の骨格。難しさは「不可避集合」と「可約性」の 2 つの箱の中に押し込められ、その中身が計算機の仕事になります。

次の定義は、検査する対象を 2 つの言葉で整理するためのものです。「配置」は地図の中に現れる小さな部分の形、「不可避集合」は「どんな地図にも必ずこのうちのどれかの形が出てくる」という形のリスト、「可約」は「その形を含む最小の反例はありえない」という性質です。リストの形がすべて可約なら、反例は存在できません。

定義 5.3（配置・不可避集合・可約配置）↗

平面グラフの一部分（頂点のいくつかと、それらの次数の情報を伴った小さな部分図）を配置と呼びます。

配置の有限集合 $\mathcal{U}$ が不可避集合であるとは、$\mathcal{U}$ のどの配置も含まないような平面三角形分割が存在しないことをいいます。言い換えれば、どんな地図も $\mathcal{U}$ の中の少なくとも 1 つの形を必ずどこかに持っている、ということです。

配置 $K$ が可約であるとは、$K$ を含む平面グラフ $G$ について、「$G$ より小さいすべての平面グラフが 4 彩色をもつ」という仮定のもとで $G$ 自身も 4 彩色をもつことが示せることをいいます。要するに $K$ は最小反例の中には現れられない、ということです。

不可避集合の全要素が可約なら、最小反例は「必ず含む形」を「含めない」ことになって矛盾します。これで証明は終わりです。

系 3.4 は、この枠組みの最も原始的な例になっています。「次数 5 以下の頂点」という 5 種類の配置は不可避集合をなします。そして六色定理の証明が示したのは、6 色の世界ではこの 5 つがすべて可約だということです。五色定理では、次数 5 の配置の可約性を示すのにケンペ鎖が必要になりました。4 色になると、この 5 つでは全然足りません。

5.2. 放電法

不可避集合を作る道具が放電法（discharging）です。1969 年に Heinrich Heesch が体系化しました。原理は素朴です。

ねらいは、不可避集合を人間が見つけられる形で作ることです。次数の小さい頂点を「お金を持っている」、次数の大きい頂点を「借金をしている」と見立てて、お金を借金のある側へ配り直し、配り終えたあとでもお金が残る頂点のまわりの形を調べます。

各頂点 $v$ に初期電荷 $6 - \deg(v)$ を与えます。三角形分割された平面グラフでは $E = 3V - 6$ が成り立つので（補題 3.3 の等号のとき）、電荷の総和は

$$\sum_{v} \bigl(6 - \deg(v)\bigr) = 6V - 2E = 6V - 2(3V-6) = 12$$

となります。頂点数が何万であろうと、総電荷はいつも 12 です。特に正電荷をもつ頂点、つまり次数 5 以下の頂点が必ず存在します。系 3.4 の別証明になっています。

ここからが放電法の本番です。「正電荷をもつ頂点から、近くの負電荷の頂点へ電荷を規則に従って移す」というルールを設計します。電荷の移動は総和 12 を変えないので、移動後もどこかに正電荷が残ります。ルールをうまく作ると、「移動後に正電荷が残るためには、その頂点のまわりが特定の形をしていなければならない」という結論が出ます。その特定の形を全部集めたものが不可避集合です。

Robertson らの証明では、32 個の放電規則から 633 個の配置からなる不可避集合が作られました。この 633 個それぞれについて可約性をコンピュータで検査します。1 つの配置の可約性検査は、境界上の彩色を全通り試し、ケンペ鎖の入れ替えを繰り返して内部に拡張できるかを調べる有限の計算です。やっていることは 表にして全部数える（例 3.3）［モンティ・ホール問題］ と同じ「場合の数え上げ」で、有限ではあるのですが、1 つの配置あたり数千から数万通りの場合を扱うため、手作業は非現実的です。

ヒント

Appel と Haken の 1976 年の証明では、不可避集合は 1936 個（後に 1482 個に整理）の配置からなり、IBM 370-168 で約 1200 時間の計算を要しました。1997 年版が 633 個まで減ったのは、可約性を検査しやすい配置だけを選んで放電規則を設計し直したからです。証明を短くする努力は、定理が示された後も続きます。

6. コンピュータが書いた証明を、人は信じられるか

1976 年 6 月、イリノイ大学は「Four colors suffice（四色で足りる）」という消印を使い始めました。数学史上まれな祝賀ですが、数学界の反応は一様ではありませんでした。

異議の中心はこうです。証明とは、原理的には一人の数学者が読んで納得できるものであるべきだ。全体を誰も読めない議論は、証明と呼べるのか。

この批判には、少なくとも 3 つの異なる論点が混ざっています。分けて考えると見通しがよくなります。

論点	内容	現在の状況
検証可能性	誰も全体を確認できないなら、正しさをどう保証するのか	1997 年版は独立に再実装され、2005 年には Coq で形式化された
誤りの可能性	プログラムのバグ、コンパイラの不具合、ハードウェア故障	形式化により論証部分の誤りはほぼ排除。処理系への信頼は残る
理解	「なぜ 4 なのか」が分からないままである	ほとんど解消していない。これは今も未解決の問い

第 1 の論点はかなり解決しました。1997 年の Robertson らの証明はプログラムが公開され、複数の独立な実装で再現されています。さらに 2005 年、Georges Gonthier は証明支援系 Coq を用いて四色定理の全体を形式化しました。放電法の議論も可約性の検査も、すべて Coq の小さな論理核が検証できる形に書き直されています。読者が信じるべきものは「Appel と Haken の Fortran プログラム」ではなく「Coq の核が正しく実装されていること」に置き換わりました。核は数千行で、多くの人が読んでいます。

第 2 の論点も、上と同じ理由でかなり弱まりました。とはいえゼロにはなりません。Coq の核にバグがない保証はありませんし、計算機が故障しない保証もありません。ただしこれは、人間が書いた長大な証明が誤りを含む可能性と、程度の差でしかないとも言えます。実際、Kempe の「証明」は 11 年間、人間の査読を通り抜けていました。

第 3 の論点だけが残っています。四色定理の証明を最後まで追っても、「なぜ 5 ではなく 4 で足りるのか」は分かりません。633 個の場合が全部たまたま可約だった、としか言えない。数学の証明には、正しさを保証する機能と、理由を教える機能の 2 つがあります。四色定理の証明は前者を果たし、後者をほとんど果たしていません。数学が難しいのは記号が多いからではなく、こういう「分かった気にならない分かり方」があるからだ、という話は 数学はなぜ難しいのか でも、証明とは何か（定義 4.1）［数学はなぜ難しいのか］ の側から触れています。

例 6.1（ドーナツの上では 7 色必要）

四色定理は平面（と球面）に固有の現象です。地図をドーナツの表面（トーラス）に描くと事情が変わります。

トーラス上には $K_7$、すなわち 7 頂点のどの 2 つも辺で結ばれたグラフを、辺が交わらないように描けます。したがって 7 国が互いにすべて隣接する地図が作れ、7 色が必要です。逆に 7 色で十分であることも証明できます。オイラーの公式がトーラスでは $V - E + F = 0$ になるので、同じ計算をやり直すと $E \le 3V$ となり、次数 6 以下の頂点の存在が出ます。あとは六色定理と同じ帰納法で 7 色に到達します。

面白いのは、この「7」の証明が四色定理よりはるかに易しいことです。Heawood は 1890 年、種数 $g \ge 1$ の曲面について必要十分な色数が

$$\left\lfloor \frac{7 + \sqrt{1 + 48g}}{2} \right\rfloor$$

であると予想しました（$g=1$ を代入すると $\lfloor (7+7)/2 \rfloor = 7$）。この予想は 1968 年に Ringel と Youngs によって証明されています。つまり穴のあいた曲面はすべて片付いていて、いちばん簡単に見える平面だけが最後まで残ったのです。

7. 演習

演習 7.1易

5 個の頂点のどの 2 つも辺で結んだグラフ $K_5$ は平面グラフでないことを、補題 3.3 を使って示してください。

解答

$K_5$ の頂点数は $V = 5$、辺数は $5$ 個から $2$ 個を選ぶ組合せの数で $E = \binom{5}{2} = 10$ です。

$K_5$ が平面グラフだと仮定します。$K_5$ は単純で $V = 5 \ge 3$ なので 補題 3.3 が適用でき、

$$E \le 3V - 6 = 3 \cdot 5 - 6 = 9$$

でなければなりません。しかし実際には $E = 10 > 9$ です。矛盾するので $K_5$ は平面グラフではありません。

なお 例 2.3 で見たとおり $K_4$ は平面に描けます（$V=4$, $E=6 \le 3\cdot4-6 = 6$ でぎりぎり通ります）。互いに隣接できる国の数は平面では 4 が上限で、これが「4 色が必要」の理由になっています。ただし「4 色で十分」がここから従うわけではないことに注意してください。$K_5$ を含まないのに 4 色が要るグラフはいくらでもあります。

演習 7.2標準

$G$ を頂点数 $V \ge 3$ の連結な単純平面グラフとし、さらに $G$ は三角形（長さ 3 の閉路）を含まないとします。このとき $E \le 2V - 4$ が成り立つことを示し、それを使って $K_{3,3}$（3 頂点ずつの 2 グループの間をすべて結んだグラフ）が平面グラフでないことを示してください。

解答

前半。 補題 3.3 の証明をなぞります。$G$ の平面描画を固定し、面の個数を $F$ とします。$G$ は三角形を含まないので、どの面の境界歩道も長さ 4 以上です。実際、境界歩道の長さが 3 であるためには長さ 3 の閉路が必要ですが、それは仮定で排除されています（長さ 1, 2 は単純性と $V \ge 3$ の連結性から排除されることも同証明のとおりです）。

各辺はちょうど 2 回だけ境界歩道に現れるので

$$2E \ge 4F, \qquad \text{すなわち} \quad F \le \tfrac{1}{2}E .$$

命題 3.1 より $F = 2 - V + E$ なので

$$2 - V + E \le \tfrac{1}{2}E .$$

両辺から $\frac{1}{2}E$ を引くと $2 - V + \frac{1}{2}E \le 0$、整理して $E \le 2V - 4$ を得ます。

後半。 $K_{3,3}$ は頂点数 $V = 6$、辺数 $E = 3 \times 3 = 9$ です。また $K_{3,3}$ は 2 部グラフなので奇数長の閉路をもたず、特に三角形を含みません（辺は必ず 2 グループの間を渡るので、閉路は必ず偶数長になります）。連結でもあります。

もし $K_{3,3}$ が平面グラフなら前半の不等式が使えて

$$E \le 2V - 4 = 2 \cdot 6 - 4 = 8$$

でなければなりませんが、実際は $E = 9 > 8$ です。矛盾により $K_{3,3}$ は平面グラフではありません。

（$K_{3,3}$ は $E = 9 \le 3V-6 = 12$ を満たすので、補題 3.3 だけでは非平面性は出ません。三角形がないという追加情報が必要でした。）

演習 7.3標準

平面上に有限本の直線を引き、平面をいくつかの領域に分割します。こうしてできる地図は必ず 2 色で塗り分けられることを示してください。

解答

直線を $\ell_1, \ldots, \ell_n$ とします。各直線 $\ell_i$ は平面を 2 つの開半平面に分けるので、各領域 $R$ に対して

$$s_i(R) = \begin{cases} 0 & (R \text{ が } \ell_i \text{ の一方の側にあるとき}) \\ 1 & (R \text{ が反対側にあるとき}) \end{cases}$$

が定まります。領域は直線をまたがない連結集合なので、$s_i(R)$ は $R$ ごとに一意に決まります。ここで

$$c(R) = s_1(R) + s_2(R) + \cdots + s_n(R) \bmod 2$$

と定め、$c(R) \in \{0, 1\}$ を色とします。

2 つの領域 $R, R'$ が隣接しているとします。共有する国境は線分（または半直線）であり、それはちょうど 1 本の直線 $\ell_k$ の一部です。$R$ から $R'$ へこの国境を横切って移動すると、$\ell_k$ に関する側だけが入れ替わり、他の $\ell_i$（$i \ne k$）に関する側は変わりません。国境の内部の点を通って移るとき、他の直線を横切らずに済むからです（国境の内部の点は $\ell_k$ 以外のどの直線にも乗っていない点として取れます）。

したがって $s_k(R') = 1 - s_k(R)$、$s_i(R') = s_i(R)$（$i \ne k$）となり、

$$c(R') = c(R) + 1 \bmod 2 \ne c(R)$$

です。よって $c$ は 2 彩色であり、直線による分割は常に 2 色で塗れます。

（同じ議論は円による分割でも通ります。「奇数回またぐと色が変わる」という発想は、桁ずらしの論証（定理 6.3）［数とは何か］ で $1 = 0.999\ldots$ を確かめる作業と同じく、不変量を作って比べる技法の一例です。）

演習 7.4難

定理 4.3 の証明で、色の個数を 5 から 4 に減らすとどこが機能しなくなるかを、証明の各段階に即して説明してください。また、次数 5 の頂点を扱う際に Kempe が必要とした「2 回の入れ替え」が、なぜ危険なのかを述べてください。

解答

（1）色が余る保証が消える。 5 色の証明では、$\deg(v) \le 4$ のとき、あるいは隣人の色が 4 種類以下のときは即座に終わりました。残ったのは「$\deg(v) = 5$ かつ隣人が 5 色を使い切る」場合だけです。4 色にすると、$\deg(v) = 4$ で隣人が 4 色を使い切る場合と、$\deg(v) = 5$ の場合の両方が残ります。前者は 5 色のときと同じくケンペ鎖 1 回の入れ替えで処理できます（$v_1$ と $v_3$ が $(1,3)$-ケンペ鎖で結ばれていなければ入れ替えて色 1 を空け、結ばれていれば 定理 4.3 と同じ平面性の議論で $v_2, v_4$ が $(2,4)$-ケンペ鎖で結ばれていないことが出ます）。問題は後者です。

（2）次数 5 では隣人の色が必ず重複する。 $\deg(v) = 5$ で色が 4 つしかないと、隣人 $v_1,\ldots,v_5$ の色は必ずどこかで重複します。現れる色が 3 種類以下なら空き色があって終わりなので、残るのは 4 色すべてが現れ、1 色だけが 2 回使われている場合です。巡回順の色が $1, 2, 3, 4, 2$ である枝を見ましょう。色 1 を空けるには $v_1$ を塗り替えたいのですが、$v_1$ と $v_3$ を結ぶ $(1,3)$-ケンペ鎖と $v_1$ と $v_4$ を結ぶ $(1,4)$-ケンペ鎖の両方が存在してしまうと、どちらの入れ替えも $v_3$ や $v_4$ を道連れにして色 1 を空けられません。ただしこの 2 本の鎖に $v$ を足した閉曲線を考えると、定理 4.3 と同じ平面性の議論から、$v_2$ を含む $(2,4)$-鎖は $v_4$ に届かず、$v_5$ を含む $(2,3)$-鎖は $v_3$ に届かないことが分かります。そこで Kempe は、この 2 本を続けて入れ替えて $v_2$ を色 4 に、$v_5$ を色 3 にし、色 2 を空けようとしました。

（3）2 回の入れ替えが危険な理由。 ケンペ鎖の定義（定義 4.1）は、その時点の彩色 $c$ に依存しています。1 回目の入れ替えを行うと彩色が $c$ から $c'$ に変わるため、$c$ に関するケンペ鎖と $c'$ に関するケンペ鎖は一般に別物です。上で入れ替える 2 本は色 2 を共有しているので、これが直接に効きます。$v_2$ を含む $(2,4)$-鎖を入れ替えると、その鎖の上で色 2 だった頂点が色 4 に、色 4 だった頂点が色 2 に変わり、$v_5$ を含む $(2,3)$-鎖の連結成分の形も変わってしまうのです。変わった後の鎖が $v_3$ まで届いてしまえば、2 回目の入れ替えは $v_3$ の色も 2 に変えてしまい、色 2 は空きません。「それぞれ単独なら正しい入れ替えが 2 つある」ことは、「2 つを続けて行ってよい」ことを意味しないわけです。

Kempe はこの依存関係を見落としました。Heawood は 1890 年、まさに合体が起きる 25 国の地図を構成し、Kempe の議論が完結しないことを示しました。定理 4.3 の証明で入れ替えを 1 回に抑えられたのは、色が 1 つ多い余裕のおかげです。

（4）だから配置を大きくする。 現代の証明はこの困難を、$v$ の近傍という「1 頂点まわりの配置」ではなく数十頂点にわたる大きな配置を扱うことで回避します。§5 で述べた 633 個の配置は、この意味で「ケンペが 1 頂点で失敗した場所を、有限個の大きな塊に分解し直したもの」です。

参考文献

• Robin Wilson, Four Colours Suffice: How the Map Problem Was Solved, Allen Lane, 2002（邦訳: ロビン・ウィルソン『四色問題』茂木健一郎訳、新潮社、2013）— 一般向けに書かれた四色問題の通史。ガスリーからアッペル＝ハーケンまでの経緯はこの本が最も詳しく読みやすいです。
• 一松信『四色問題 その解決と展開』講談社ブルーバックス、1978 — アッペル＝ハーケンの証明直後に書かれた日本語の解説。放電法と可約性の考え方を数式付きで追えます。
• N. Robertson, D. Sanders, P. Seymour, R. Thomas, “The four-colour theorem”, Journal of Combinatorial Theory, Series B 70 (1997), 2–44 — 現在標準とされる証明。633 個の配置と 32 個の放電規則による構成。
• G. Gonthier, “Formal Proof — The Four-Color Theorem”, Notices of the American Mathematical Society 55 (2008), 1382–1393 — 証明支援系 Coq による完全形式化の報告。PDF
• R. Diestel, Graph Theory, 5th ed., Springer, 2017 — 第 5 章 Colouring に五色定理の証明と四色定理の証明の概略があります。オイラーの公式は第 4 章。
• J. A. Bondy, U. S. R. Murty, Graph Theory, Springer GTM 244, 2008 — 平面グラフと彩色の標準的な教科書。放電法の入門的な解説を含みます。

Appendix: 四色定理と同値な言い換え

辺の塗り分けとしての四色定理。 1880 年、Peter Guthrie Tait は四色問題を辺の彩色の問題に翻訳しました。地図の境界線をすべて 3 本ずつ集まるようにした状況（各頂点の次数が 3 の平面グラフ、すなわち 3-正則平面グラフ）で考えると、次が成り立ちます。橋（取り除くと連結成分が増える辺）をもたない 3-正則平面グラフの面が 4 彩色できることと、その辺を 3 色で塗り分けられること（隣り合う辺が異なる色になるように）は同値です。

翻訳の仕掛けは、4 つの色を $\{0, a, b, c\}$ というクラインの四元群の元と見ることです。各辺の色を、その両側の面の色の群における和として定めると、面の 4 彩色から辺の 3 彩色が、逆に辺の 3 彩色から面の 4 彩色が復元できます。

Tait の失敗。 Tait はさらに「橋をもたない 3-正則平面グラフはハミルトン閉路（すべての頂点をちょうど 1 回ずつ通る閉路）をもつ」と仮定しました。ハミルトン閉路があれば辺の 3 彩色は簡単に作れるので、これで四色定理が従うはずでした。しかしこの仮定は偽です。1946 年、W. T. Tutte が 46 頂点の反例を構成しました。Kempe の誤りが 11 年で見つかったのに対し、Tait の誤りは 66 年生き延びたことになります（誤りの所在自体は 1891 年に Julius Petersen が指摘していました）。

教訓。 四色問題は、正しそうな補題を 1 つ挟むだけで一気に易しくなる、という性質を繰り返し示してきました。そしてその補題はことごとく偽でした。何十例で確かめても反例が出うることは、40 回当たって 41 回目に外れる公式（例 4.2）［数学はなぜ難しいのか］ と同じ教訓です。有名な数学者たちがこの問題で足を滑らせた記録については 有名な数学者 も併せて読んでみてください。証明の歴史とは、正しい定理の歴史であると同時に、もっともらしい誤りの歴史でもあります。