【数学・四色定理】どんな地図も「4色」で塗れるのに、なぜ証明に124年かかったのか？

世界地図でも、日本の都道府県の地図でも、ゲームに出てくる架空の大陸でもかまいません。隣り合う国が同じ色にならないように塗り分けるとき、色は4色あれば必ず足ります。これを「四色定理（ししょくていり）」といいます。

ルールは小学生でも理解できます。ところが、この当たり前に見える事実を証明するのに、数学者たちは124年かかりました。しかも最後に決着をつけたのは、紙とペンではなく、コンピューターによる1,000時間以上の計算でした。

問題の意味がわかることと、それを証明できることのあいだには、ときにとてつもない距離があります。その距離がどこから生まれるのかを、順に見ていきます。

真ん中に1つの国があり、そのまわりを5つの国がぐるりと囲んでいる地図を考えます。これを3色で塗れるか、試してみてください。

真ん中の国は周りの5カ国すべてと接している。3色だと、最後の1国に塗れる色が残らない。

真ん中の国に1色使うと、周りの5カ国は残りの2色だけで、交互に塗っていくしかありません。ところが周りは5カ国、つまり奇数です。1・2・1・2と進めると、最後の国は両隣が1と2になり、真ん中の色も使えないので、塗れる色がなくなります。

つまり、わかっていることは2つあります。

「足りない例を1つ見せる」のと、「どんな場合でも足りると示す」のとでは、難しさがまったく違います。後者は、無限にある地図すべてについて言い切らなければならないからです。

四色定理には、但し書きが2つあります。

但し書き1　点で接しているだけなら「隣」ではない

アメリカには「フォー・コーナーズ」という、ユタ・コロラド・ニューメキシコ・アリゾナの4州が1点で交わる場所があります。このとき、対角の位置にある州どうしは点で触れているだけなので、同じ色で塗ってかまいません。「隣り合う」とは、長さのある境界線を共有していることを指します。

もし点で接するだけでも隣と数えてしまうと、ピザのように切り分けた地図では中心に何十カ国でも集められるので、色がいくらあっても足りなくなります。

但し書き2　飛び地は認めない

アメリカ本土とアラスカ、ロシア本土とカリーニングラードのように、1つの国が離れた場所に分かれている地図は対象外です。飛び地を同じ色で塗る決まりにすると、5色以上が必要な地図を作れてしまいます。四色定理は、どの国も「ひとつながりの領域」であることを前提にしています。

左：4つの国が1点で交わる場合。対角の国は同じ色にできる。　右：5の国が外側と中心の2か所に分かれていると、5カ国すべてが互いに隣り合い、5色が必要になる。

前半は正しい事実です。平面の上では、互いに全部隣り合う国は4カ国までしか作れません。けれども、そこから「4色で足りる」は出てきません。

さきほどの地図を思い出してください。あの地図で「互いに全部隣り合っている」のは、真ん中の国と、周りの隣どうしの2カ国を合わせた3カ国までです。4カ国が全部隣り合っている場所はどこにもありません。それなのに、4色が必要でした。

色が足りなくなる原因は、すぐ近くの国どうしの関係だけではありません。ある国の色を決めると隣の国の選択肢が減り、それがさらに隣へ伝わって、遠く離れた国の色まで縛ってしまいます。この連鎖こそが、四色定理の難しさの正体です。

4色の難しさは、色を多いほうから1つずつ減らしていくと、はっきり見えてきます。ここからは、国を点で、隣り合う関係を線で表して考えます。

出発点　「隣が5カ国以下の国」が必ずある

どれほど入り組んだ地図でも、すべての国が6カ国以上と隣り合うことはできません。隣国が5カ国以下の国が、必ずどこかに1つはあります。高校の数学Aで学ぶ「オイラーの多面体定理」から導ける事実です。

6色　取り除いて、戻すだけ

隣国が5カ国以下の国を A とし、A の点をいったん図から取り除きます。国が1つ減った地図が6色で塗れているとして、A を元に戻します。A の隣は多くても5カ国なので、周りがすべて違う色でも、6色あれば必ず1色余ります。それを A に塗れば終わりです。

「国が1つ少ない地図が塗れるなら、1つ多い地図も塗れる」。これを国の数が少ないほうから順に積み上げていくのが数学的帰納法、いわばドミノ倒しです。6色なら、工夫は何も要りません。

5色　色を入れ替えて、1色あける

5色にすると、困る場面が1つだけ出てきます。A の周りの5カ国が、ちょうど5色すべてを使っている場合です。余っている色がありません。

ここで使うのが、1879年にイギリスのアルフレッド・ケンプが考え出した「色の入れ替え」です。A の周りの5カ国を順に 1・2・3・4・5 の色とし、まず 1 の国から出発して、「1 と 3 の色だけ」をたどって進める範囲を調べます。

1と3が交互に並ぶ鎖（太線）が A とつながって輪になると、2の国は内側に閉じ込められ、外側の4の国とは「2と4の鎖」でつながれない。

どちらの場合でも、A に塗る色が1つ空きます。この技法はケンプ鎖と呼ばれています。

6色なら、何もしなくていい。5色なら、色を1回入れ替えればいい。ここまでは、1色減らすごとに工夫が1つ増えるだけでした。

同じ作戦を4色で試します。A の隣が4カ国までなら、5色のときと同じ「壁」の論法がそのまま通用します。

崩れるのは、A の隣が5カ国ある場合です。色は4色しかないので、周りの5カ国が4色すべてを使っているとき、どれか2カ国は同じ色になっています。A に色をあけるには、その2カ国を両方とも別の色に変えなければならないことがあり、色の入れ替えが2回必要になります。

ケンプは、こう考えました。1回目の入れ替えはできる。2回目の入れ替えもできる。だから、両方できる。

落とし穴はここでした。1回目の入れ替えをすると、色のつながり方そのものが変わります。国が9つだけの小さな例で確かめてみます。

国が9つの例。A の周りの色は 1・2・3・4・2。下の図の白い輪は、1回目の入れ替えで色が変わった2カ国。

こうなると、2回目の入れ替えをしても、A の周りには4色が残ったままです。順番を逆にしても、同じことが起こります。

念のために言えば、この地図そのものは、別の塗り方をすれば4色で塗れます。うまくいかなかったのは地図ではなく、ケンプの手順のほうです。

6色から5色へ1つ減らすには、ひとつの工夫で足りました。5色から4色へもう1つ減らすには、同じ工夫では届きませんでした。

ケンプはこの落とし穴に気づかないまま、1879年に「四色定理を証明した」と発表しました。そして証明は、11年間、正しいものとして受け入れられます。世界中の数学者が読み、納得していたのです。

誤りを見つけたのは、1890年のパーシー・ヒーウッドでした。2回の入れ替えが実際に失敗する地図を、具体的に描いてみせたのです。

ただ、ヒーウッドは壊しただけではありません。同じ論文で、ケンプ鎖を使えば「5色なら必ず足りる」ことは証明できると示しました。さきほどの5色の証明は、このときのものです。証明は崩れても、道具は残りました。

1890年に振り出しへ戻ってから、次の決着まで86年。そのあいだ、四色問題は未解決のまま残りました。

1976年、アメリカ・イリノイ大学のケネス・アッペルとヴォルフガング・ハーケンが、四色定理の証明を発表しました。発想はケンプの方法の延長線上にあります。

この2つがそろえば、4色で塗れない地図は存在できません。無限にある地図の問題を、約1,500個の部品の確認に置き換えた。ここまでが人間の発見です。

残ったのは確認の作業でしたが、その量は人の手に負えるものではありませんでした。2人は大学の大型コンピューターを1,000時間以上動かして、すべてを調べ上げます。イリノイ大学の数学科は、郵便物に押すスタンプを「FOUR COLORS SUFFICE（4色で足りる）」に変えて、これを祝いました。

部品の数は、発表当初の1,900個あまりから最終的に1,482個へと整理されたため、資料によって数字が少し違います。

「それは証明と呼べるのか」

数学界の反応は、祝福だけではありませんでした。

数学の証明とは、読んだ人が「なるほど、だからそうなるのか」と納得できる筋道のことだ、と多くの数学者は考えていました。答えは正しいらしいが理由が見通せない、という状況は、それまでの数学にはほとんどなかったものです。

その後、1996年には別のチームが場合の数を633個に減らした証明を作り、2005年には証明の全体が専用のソフトウェアで1行ずつ検証されました。現在、四色定理の正しさを疑う数学者はほとんどいません。それでも、人間が紙の上で読み通せる短い証明は、いまだに見つかっていません。

ところが、舞台を少し変えると話は逆転します。もし地球が球ではなく、真ん中に穴のあいたドーナツ型だったら、地図の塗り分けには何色必要でしょうか。

答えは7色です。そしてこちらは1890年、ヒーウッドが紙とペンだけで証明を終えています。球面の4色より86年も早い決着でした。

7色は必要 ― 7カ国が全部隣り合う地図がある

平面では、互いに全部隣り合う国は4カ国までしか作れませんでした。ドーナツの表面では、穴をくぐる道と外を回る道の両方が使えるので、7カ国が全部お互いに隣り合う地図を描けます。7カ国が全部隣どうしなら、7色なければ塗れません。

ドーナツの表面を切り開いて平らに広げた図。白い枠で囲んだ7カ国がドーナツ1個分で、薄い部分は同じ地図の繰り返し（枠の端は、ドーナツの上では反対側の端につながっている）。どの国も、自分以外の6色すべてと接している。

7色で十分 ― 色の入れ替えすら要らない

ドーナツ型では、オイラーの公式が V − E + F = 0 に変わります。同じ計算をすると、今度は「隣が6カ国以下の国が必ずある」ことがわかります。

あとは6色のときと同じドミノ倒しです。隣が6カ国以下の国 A を取り除き、残りを7色で塗り、A を戻す。周りの6カ国がすべて違う色でも、7色あれば必ず1色余ります。色の入れ替えは一度も必要ありません。

なぜ、複雑な形のほうが簡単なのか

「取り除いて戻すだけ」の単純な議論でわかるのは、球や平面では6色、ドーナツでは7色までです。ドーナツでは、その7色がそのまま本当の答えでした。簡単にわかる上限と、実際に必要な色の数が、最初から一致していたのです。

球や平面では、そのあいだに2色ぶんのすき間があります。1色ぶんを埋めたのがケンプ鎖、残りの1色ぶんを埋めたのがコンピューターでした。形はドーナツのほうが複雑なのに証明はずっと短い。その理由は、埋めるべきすき間が最初からなかったことにあります。

YBA教育研究会では、各教科の学習を、単なる暗記や作業ではなく、「なぜそうなるのか」を考えるところから指導しています。

世田谷・経堂で完全1対1の個別指導をお探しの方は、ぜひご覧ください。　→ 経堂の完全1対1個別指導｜YBA教育研究会の指導内容はこちら