東京23区を｢最も少ない色｣で塗り分けるには何色必要か…解決まで124年もかかった数学の超難問を解説する

出所＝『笑わない数学』

多くの数学者を悩ませてきた「四色問題」とはどのようなものか。パンサー尾形貴弘が難解な数学の世界を大真面目に解説するNHKの知的エンターテインメント番組「笑わない数学」の放送内容を再構成した書籍より、一部を紹介する――。

※本稿は、NHK「笑わない数学」制作班編『笑わない数学』（KADOKAWA）の一部を再編集したものです。

■「少ない数の色」で地図を塗り分ける方法

次の図は東京23区の地図です（図表1）。

これから、この地図を隣の区が同じ色にならないように塗り分けていきます。ただし、できるだけ少ない数の色で塗り分けます。

まずは、赤と青の2色で塗り分けられるかみてみましょう。

港区を赤、中央区を青で塗ると、両方の区に隣接する千代田区は赤でも青でも塗り分けることができません（図表2）。

出所＝『笑わない数学』

それでは、赤色と青色に黄色を加えた3色であればどうでしょうか？　千代田区を黄色で塗ることができます。

そして、新宿区は港区と千代田区に隣接するので青色、文京区は千代田区と新宿区に隣接するので赤色に塗り分けることができます。

すると、台東区は中央区、千代田区、文京区の3区に隣接するため、赤でも青でも黄でも塗り分けることができません（図表3）。

出所＝『笑わない数学』

それでは、赤色、青色、黄色に緑色を加えた4色あればどうでしょうか？　台東区を緑色で塗ることができます。

さらにどんどん塗り分けていくと、4色あれば東京23区をすべて塗り分けることができました（図表4）。

出所＝『笑わない数学』

同じように、日本地図も4色で塗り分けられます（図表5）。

出所＝『笑わない数学』

■世紀の難問「四色問題」とは

これまでの説明で「四色問題」がどのような問題か、おわかりいただけたのではないかと思います。

そうです。世の中のすべての地図は、4色あれば塗り分けられるのではないか、それをどうやったら証明できるのかが、世紀の難問「四色問題」なのです。

この問題は、1852年イギリスのロンドンで、ある若者が「どんな地図でも4色で塗り分けることができそうだ」と気がついたことから始まったと言われています。

その話を聞いたイギリスを代表する数学者の一人、オーガスタス・ド・モルガンは、このことを数学的に厳密に証明しようと思い立ちます。

しかし、ド・モルガンは証明に大苦戦。彼が学者仲間にこの難問をなげかけていったことで、四色問題は世に広まっていったのです。

ド・モルガン以外にも多くの数学者が四色問題に挑戦しましたが、誰も証明には到達できず、時間だけが流れていきました。

しかし、問題が生まれて27年後の1879年に四色問題を大きく前進させる論文が発表されました。

その論文の著者はアルフレッド・ケンプというロンドンで働く弁護士でした。

■「箱に入った地図を4色で塗り分けられるか」

ケンプはまず、ありとあらゆる地図を「国の数で地図を分類する」ことから始めました。それはつまり、下の図のように、1カ国の地図すべてが入った箱、2カ国の地図すべてが入った箱、……、100カ国の地図すべてが入った箱、……、10000カ国の地図すべてが入った箱、……とすべての地図を国の数で分類したのです（図表6）。

出所＝『笑わない数学』

そして、それぞれの箱に入った地図が4色で塗り分けられるか考えたのです。

1カ国の地図たちは当然4色で塗り分けられますよね。1カ国しかない地図なのですから、4色のうちどれかの色で塗ってしまえば塗り分けられます。

つまり、1カ国の地図すべてが入った箱は4色で塗り分けOK。

同じように、2カ国の地図すべてが入った箱も、3カ国の地図すべてが入った箱も、4カ国の地図すべてが入った箱も4色で塗り分けOKということがわかります。

■難問解決のカギとなる仮定

では、この調子で5カ国すべてが入った箱、6カ国すべてが入った箱、……も4色で塗り分けOKと証明できるでしょうか？　もしかしたら塗り分けOKと証明できるかもしれません。

ただ、何カ国の地図まで塗り分けられるかわからないので、とにかく1カ国の地図すべてが入った箱から、nカ国の地図すべてが入った箱までが4色で塗り分けOKになったと仮定したのです。

そして、ケンプはこんなことを言いました。

「1カ国の地図すべてが入った箱から、nカ国の地図すべてが入った箱まで、すべての箱が4色で塗り分けOKならば、次のn＋1カ国の地図すべてが入った箱も自動的にOK」という“都合の良いこと”がもしあれば、凄いことが起きるぞ‼

もし、ケンプの言っている“都合の良いこと”が本当にあるのなら、nカ国までの箱が全部OKだということから、n＋1カ国の箱も自動的に全部OKということになります。

そして、さらに“都合が良いこと”によってn＋2カ国の箱も自動的にOK、n＋3カ国の箱もOK、……というように、まるでOKサインのバケツリレーのように、無限に続くすべての箱がOKだということがいえてしまいます。

出所＝『笑わない数学』

つまり、この“都合が良いこと”が実際にあることが示せれば、四色問題は解決できるのです。

■「都合が良いこと」は本当に正しいのか

この先の目標は、この“都合が良いこと”が本当に正しいのかを確かめることです。

ケンプは次のことに着目します。

どんな国にも「二辺国」「三辺国」「四辺国」「五辺国」と呼ばれる国のいずれか1つは必ず含まれる。

次のように、二カ国に接している国を「二辺国」、三カ国に接している国を「三辺国」、四カ国に接している国を「四辺国」、五カ国に接している国を「五辺国」と呼びます（図表8）。

出所＝『笑わない数学』

ケンプが着目した事実を、まだ4色で塗り分けOKとわかっていないn＋1カ国の箱に当てはめてみると、箱の中の地図たちは「二辺国」を含む地図、「三辺国」を含む地図、「四辺国」を含む地図、「五辺国」を含む地図の4つに分類できるのです。

出所＝『笑わない数学』

ここからは、箱の中で4つに分類された地図がそれぞれ4色で塗り分けられるか考えていきます。

■ケンプの「天才的な発想」

まず、二辺国を含む地図について考えていきましょう。

ここで、ケンプは二辺国を消して考えてみるということを思いつきました（図表10）。

出所＝『笑わない数学』

二辺国を消したこの地図の国の数は1カ国減りnカ国の地図になりました。nカ国の地図は、すべて4色で塗り分けできると仮定しているので、このnカ国の地図は4色で塗ることができます（図表11）。

出所＝『笑わない数学』

ここで、先ほど消してしまった二辺国を復活させます。

すると、二辺国は接している二カ国とは別の色で塗ることができますので、地図全体を4色で塗り分けられたということになります（図表12）。

出所＝『笑わない数学』

つまり、二辺国をひとつでも含むn＋1カ国の地図は、すべてこの方法で塗り分けOKだと証明できたことになります。

三辺国を含む地図、四辺国を含む地図も、同じように、1カ国減らして4色で塗り分けし、国を復活させて色を塗るという方法で塗り分けOKだと証明できます（図表13）。

（実は、四辺国を含む地図は単純にはいかないのですが、ケンプの天才的な発想で証明できます。）

出所＝『笑わない数学』

■最後の関門「五辺国」

四辺国を含む地図まで4色で塗り分けられることがわかったのですから、残るは五辺国をひとつでも含むn＋1カ国の地図が4色で塗り分けられるかどうかです。

ケンプは1879年に発表した論文で、そのことを証明しましたが、その11年後に誤りであることが見つかります。

ケンプの方法では証明できないということがわかった後、多くの数学者たちが新しいアイデアを用いて証明に挑んだものの、長い間誰一人成功しませんでした。

しかし、20世紀にはいると、そんな絶望的な状況に僅かな希望を与える新たな証明方法が考案されます。

その方法とは、五辺国を含む地図をさらに細かく分類して、塗り分けられるか調べてみようというものです。

実は、五辺国を含む地図は、さらに次のように2つに分類できるのです（図表14）。

出所＝『笑わない数学』

分類した2つをそれぞれ4色で塗り分けられることを証明できれば解決です。

しかし、この方法でも、誰も証明にたどり着くことはできませんでした。

数学者たちは、さらに分類を行い、それでも駄目ならさらに分類することを繰り返すことになりました。

この方法で、4色で塗り分けられる分類をいくつか見つけることができたのですが、爆発的に増えていく分類は段々と手に負えなくなっていきました。

出所＝『笑わない数学』

■エレファント（elephant）な証明による決着

この作業はいつ終わるのか？　そもそも終わりはあるのか？　こうして四色問題の証明は人間には到達できない無謀な挑戦だと恐れられるようになっていきました。

四色問題が生まれて1世紀以上が過ぎた1970年代に、アメリカの数学者ウォルフガング・ハーケンとケネス・アッペルが、コンピュータで膨大な証明作業に挑んだのです。

そして、コンピュータを用いた計算開始から4年後、遂にコンピュータが証明の完了を告げます。

実に124年の時を経て、四色問題は解決されました。

NHK「笑わない数学」制作班編『笑わない数学』（KADOKAWA）

しかし、この証明は批判を浴びてしまいます。

当時の数学者は、コンピュータによる証明に馴染みがなかったため懐疑的な声があがったのです。

さらに、ひたすら分類を行う証明スタイルは泥臭すぎて「美しくない」とも言われ、「エレガントな証明」（elegant proof）を期待していた人からは「エレファントな証明」（elephant proof）と言われてしまったのです。

今ではコンピュータを使う証明も立派な証明方法とされています。しかし一方で、人間が本来持つ知性の底力を見せつけるような「エレガントな証明」が期待されているのも、また事実なのです。

----------

NHK「笑わない数学」制作班 パンサー尾形貴弘が難解な数学の世界を大真面目に解説する異色の知的エンターテインメント番組。レギュラー番組としてNHK総合テレビで、シーズン1が2022年7月から9月まで、シーズン2が2023年10月から12月まで放送された。シーズン1はギャラクシー賞テレビ部門の2022年9月度月間賞に選ばれた。過去の番組はNHKオンデマンドやDVDで確認することができる。

----------

（NHK「笑わない数学」制作班）