四色問題とは？わかりやすく｜どんな地図も4色でぬれる？だれがいつ解いた・コンピューター証明

四色問題とは？（ひとことで）

四色問題とは、「どんな地図でも、となり合う国がちがう色になるように、4色あればぬり分けられるか」という問題です。1852年にイギリスのフランシス・ガスリーが気づき、1976年にアメリカ・イリノイ大学のアッペルとハーケンが、コンピューターを使って「4色でかならずぬり分けられる」と証明しました。今は四色定理とよばれます。

問題の意味は小学生にも分かるのに、証明までに124年かかりました。しかも、その証明は人間が手で確かめきれないほどの量の場合分けをコンピューターに調べさせたもので、「コンピューターを使った証明は、本当に証明と言えるのか」という大きな議論も生みました。

中学受験の算数では色の塗り分け問題（何通りあるか）がよく出ますが、その「となりは別の色」というルールこそが四色問題の出発点です。数え方の土台は順列・組合せの公式や場合の数とはにもつながっています。

四色問題の意味をやさしく解説

ルールは2つだけ

四色問題で考える「地図」には、次の決まりがあります。

• となり合う国は、ちがう色にする：ここで「となり合う」とは、境界線（線の長さ）を共有していることです。
• 1点だけで接している国は、となりとは考えない：ケーキを十字に切ったときのように、まん中の1点だけで接する国どうしは同じ色でかまいません。

もう一つ、国は1つにつながった形（飛び地がない）とします。飛び地を認めると、同じ国を同じ色にしなければならない制限が増え、4色では足りない地図が作れてしまうからです。

3色では足りない

まず「3色で足りるか」を考えてみましょう。まん中の国Aを、3つの国B・C・Dが取りかこむ地図を作ると、4つの国はどの2つもとなり合っています。だから4つともちがう色にするしかなく、3色では足りません。

では、5つの国がどれもたがいにとなり合う地図は作れるでしょうか。平面の上では、どうがんばっても作れないことが分かっています。でも「5つが全部となり合わない」ことと「4色で足りる」ことは同じではありません。となり合わない国どうしにも、色の選び方のしわ寄せがつながっていくからです。ここが四色問題の本当のむずかしさです。

地図を「点と線」に置きかえる

数学者は、地図を国＝点、となり合う＝線に置きかえて考えます。こうすると四色問題は、「平面に交わらずにかける点と線の図（平面グラフ）なら、線でつながった点どうしがちがう色になるように4色でぬれるか」という問題になります。

このように、点と線のつながりだけを考える数学をグラフ理論といいます。グラフ理論は、オイラーの業績と生涯が1736年に解いたケーニヒスベルクの橋の問題（一筆書き）から始まりました。四色問題は、グラフ理論を大きく育てた問題でもあります。

身のまわりの「ぬり分け」

四色問題のルールは、地図だけの話ではありません。たとえば学校の定期テストの時間割を作るとき、同じ生徒が受ける2つの科目を同じ時間に置くことはできません。科目を「国」、同じ生徒が受ける科目どうしを「となり」と考えると、時間割づくりは「時間＝色」のぬり分け問題になります。ただし時間割の場合は、となり方が平面の地図よりずっと複雑になることがあり、4色（4つの時間）で足りるとはかぎりません。四色定理が保証してくれるのは、あくまで平面の上にかける地図の場合だけです。

四色問題の歴史と年表

1852年：イギリスの地図をぬっていて気づいた

1852年、ロンドンの大学を出たばかりのフランシス・ガスリーは、イギリスの州の地図をぬり分けているときに、「4色あれば足りるのでは？」と気づいたと伝えられています。弟のフレデリックを通じて、この問題は数学者ド・モルガンに伝わりました。ド・モルガンは同じ年、アイルランドの数学者ハミルトン（四元数の発見者）への手紙でこの問題を紹介しています。

1879年：「証明できた」…はずだった

1878年、イギリスの数学者ケーリー（行列の計算の研究者）がロンドン数学会でこの問題を取り上げ、広く知られるようになります。翌1879年、弁護士でもあったアルフレッド・ケンプが証明を発表し、問題は解決したと考えられました。

1890年：11年後に見つかった誤り

ところが1890年、パーシー・ヒーウッドがケンプの証明に誤りがあることを見つけます。ヒーウッドはケンプの方法を使って「5色あれば足りる」（五色定理）ことは正しく証明しましたが、4色についてはふたたび未解決にもどってしまいました。

1976年：コンピューターによる証明

そこから80年以上、多くの数学者が挑みました。1976年、イリノイ大学のケネス・アッペルとヴォルフガング・ハーケンは、どんな地図にも必ずふくまれる「部品の形」を2000個近くにしぼり、その一つひとつが「4色の妨げにならない」ことをコンピューターで確かめて、証明を完成させました。コンピューターの計算時間は1000時間をこえたといわれます。

なぜ80年以上も解けなかった？

ヒーウッドの発見のあと、多くの数学者がケンプの方法を直そうとしました。20世紀に入ると、ドイツのハインリッヒ・ヘーシュが「放電法」という考え方を作り、「どんな地図にも必ずふくまれる部品のリストを作り、その部品を1つずつ調べればよい」という道筋を示しました。ところが、そのリストは何千個にもなる見こみで、人の手では調べきれません。アッペルとハーケンは、このヘーシュの考えを受けつぎ、ちょうど性能が上がってきた大学のコンピューターを使うことで、ようやくゴールにたどり着いたのです。数学の発見と、計算する道具の進歩がかみ合ってはじめて解けた問題だといえます。

四色問題はいつ・だれが解いた？

四色問題は、1976年に、アメリカのイリノイ大学のケネス・アッペルとヴォルフガング・ハーケンが解きました。論文は1977年に発表されています。イリノイ大学の郵便局では、記念に「Four Colors Suffice（4色で足りる）」という消印が使われたことでも知られています。

証明の考え方（ざっくり）

証明は「背理法」の形をとります。

1. もし4色でぬれない地図があるとしたら、その中で国の数がいちばん少ないものを考える。
2. どんな地図にも、決まったリストの中の「部品」のどれかが必ずふくまれることを示す（これを「不可避集合」といいます）。
3. その部品は、どれも「その部分をいったん取り除いてぬってから、もとにもどしても4色でぬれる」形であることを示す（「可約」といいます）。
4. すると「いちばん小さい、4色でぬれない地図」より小さい地図で4色でぬれないものが作れてしまい、矛盾する。だから4色でぬれない地図はない。

このうち③の「部品を1つずつ確かめる」作業が膨大で、人の手ではとても終わりませんでした。そこをコンピューターが担当したのです。数学的帰納法（数学的帰納法とは）の考え方にも似た、「小さいほうへ小さいほうへ」と追いつめる証明です。

その後の確認

コンピューターのプログラムにまちがいがないか、という疑問は長く残りました。1996年にはロバートソンら4人が、部品の数を633個に減らした、より確かめやすい証明を発表しました。さらに2005年には、ゴンティエらが、証明全体を「証明を確かめるためのソフトウェア」で一歩ずつ検査し、正しいことを確かめたと発表しています。今では四色定理は、正しい定理として広く受け入れられています。

四色問題はなぜ難しかったのか

1. 地図が無限にある

1枚の地図なら、ためしにぬってみれば確かめられます。でも問題は「すべての地図」です。国の数はいくらでも増やせるので、全部を調べることはできません。だから「どの地図にも共通する性質」を見つける必要がありました。

2. 「5色」と「4色」の差が大きすぎた

ヒーウッドの五色定理は、数ページで証明できます。ところが、色を1つ減らして4色にしたとたん、証明は何百ページ分もの場合分けとコンピューター計算が必要になりました。ほんの少しの差が、とてつもない難しさの差になる――これは数学の難問によくあることです。

3. 人間が確かめきれない

アッペルとハーケンの証明は、部品の数が多すぎて、人が1つずつ読んで確かめることが事実上できませんでした。「紙と鉛筆で確かめられない証明は証明なのか」という議論は、数学者の間でも長く続きました。今では、コンピューターで確かめる証明はケプラー予想（球の詰め込み問題）などでも使われ、数学の新しい道具になっています。

よくある誤解：「5つの国が全部となり合わなければ4色で足りる」？

「どの5つの国もたがいにとなり合うことはできない。だから4色で足りるはずだ」と考える人は少なくありません。実は、ケンプの「証明」も、これに近い「なんとなく正しそう」な部分に落とし穴がありました。ある国の色を変えると、その影響がとなりへ、さらにそのとなりへと鎖のように広がり、遠くはなれた国の色の選び方にまでしわ寄せがくることがあります。このため、「近くの5つだけを見ればよい」とはいえないのです。この「色を入れかえる鎖」は、のちにケンプ鎖とよばれ、四色定理の正しい証明でも重要な道具として使われています。

また、「世界地図の国は4色でぬれているから正しい」というのも証明にはなりません。実際の地図が4色でぬれることは、たくさんの例の一つにすぎず、「どんな地図でも」を示したことにはならないからです。数学で「すべての場合に成り立つ」と言うためには、例をいくつ集めても足りず、理由をつけた証明が必要です。この点は、ゴールドバッハ予想（偶数は素数2つの和？）やコラッツ予想（3n＋1問題）のように、コンピューターでとても大きな数まで確かめられているのにまだ「証明」がない問題と同じです。

4. 「ドーナツの上」なら答えがちがう

おもしろいことに、平面ではなくドーナツの表面（トーラス）の上の地図では、7色必要な地図があり、7色あれば足りることが分かっています。7色で足りることは1890年にヒーウッドが示しています。穴の数がもっと多い形も含めた一般の場合は、1968年にリンゲルとヤングスが証明しました。平面の4色のほうが証明がずっとむずかしかったのです。形と「となり合い方」の関係は、ポアンカレの業績（位相幾何学）が育てた位相幾何学ともつながっています。

受験・勉強と四色問題のつながり

中学受験：ぬり分けの場合の数

中学受験の算数では、「図の部分を、となり合う部分がちがう色になるように4色でぬり分けると、何通りか」という問題がよく出ます。

この図では、イとウがほかの全部ととなり合っているので、イとウから先に色を決めるのがコツです。イは4通り、ウは残り3通り。アはイ・ウとちがう色なので2通り、エもイ・ウとちがう色なので2通り。全部で4×3×2×2＝48通りです。「となりの多い部分から先にぬる」は、四色問題の証明でも使われる考え方です。

自由研究にも：日本地図を4色でぬってみよう

白地図を用意して、47都道府県を「となりの県とちがう色」になるようにぬってみると、四色問題を体で感じられます。ぬり方のコツは、となりの県が多い県から先に色を決めることです。たとえば長野県は8つの県ととなり合っていて、日本でいちばんとなりが多い県として知られています。こういう県を先に決めておくと、あとで色が足りなくなりにくくなります。

ただし、日本地図には一つ注意点があります。和歌山県の北山村のように、ほかの県に囲まれた飛び地があるのです。四色定理は「国が1つにつながっている地図」についての定理なので、飛び地まで同じ色にしようとすると、条件が変わってしまいます。実際にぬるときは、海でへだてられた島（北海道・沖縄など）は陸でとなり合わないので、色の制限がゆるいことにも気づくはずです。「どの条件で、何が言えるのか」をはっきりさせることは、数学の問題を読むときにも大切です。

高校受験・大学受験：場合の数と証明

大学受験の数学Aでも、正多面体の面のぬり分けや、円順列を使ったぬり分けが出題されます。また、「どんな場合も成り立つ」ことを示す証明問題では、四色問題の証明と同じく背理法や数学的帰納法が活躍します。命題と証明の考え方を確かめておきましょう。

勉強法として：「全部」を相手にするときの考え方

四色問題から学べるのは、「無限にあるものを、有限個のパターンに分けて調べる」という考え方です。入試の場合分けの問題でも、まずは「どんな場合があるか」を整理し、もれなく・重なりなく分けることが大切です。数学オリンピックの問題にも、この考え方を使うものがたくさんあります（数学オリンピックの問題（長方形に詰めた正方形））。数学の勉強の進め方は数学の勉強法（解法の暗記→演習→過去問）も参考にしてください。

四色問題が数学にあたえた影響

• グラフ理論の発展：四色問題に挑む中で、点と線のつながりを研究するグラフ理論が大きく育ちました。今では、カーナビの道案内、電車の乗りかえ案内、SNSのつながりの分析など、身のまわりの多くの技術に使われています。
• コンピューターによる証明：四色定理は、コンピューターが本質的な役割をはたした最初の大きな証明です。その後、ケプラー予想の証明などにも同じ方法が使われました。
• 「証明とは何か」を考えなおすきっかけ：人が読みきれない証明をどう信じるか、という問いは、証明をコンピューターで1行ずつ確かめる「形式的証明」の研究につながりました。
• 色をぬる問題の広がり：試験の時間割づくり（同じ生徒が受ける科目を同じ時間にしない）や、携帯電話の電波の割り当て（近い基地局に同じ周波数を使わない）も、「となりは別の色」というぬり分けの問題として考えられます。コンピューターの世界の難問P≠NP予想にも、ぬり分けの問題が登場します。

四色定理は「4色あれば必ずぬれる」ことを教えてくれますが、「実際にどうぬればよいか」をすばやく見つける方法については、今もコンピューター科学の研究が続いています。さらに、ある地図が3色でぬれるかどうかを判定する問題は、地図が大きくなると急にむずかしくなることが知られていて、P≠NP予想の代表的な例としてよく取り上げられます。「4色なら必ずできる」のに「3色でできるかを見分ける」のはむずかしい――このちがいも、ぬり分けの問題のふしぎなところです。

四色問題に挑戦！練習問題

四色問題と関係する数学者・難問

• オイラー（グラフ理論の生みの親）：ケーニヒスベルクの橋の問題でグラフ理論を始めました。
• ケーリー：1878年に四色問題を数学界に広めました。
• ハミルトン：ド・モルガンが最初に四色問題を手紙で伝えた相手です。
• メビウス（メビウスの帯）：四色問題とよく似た「5人の王子の問題」を講義で出したといわれ、四色問題と混同されることもあります。
• ケーニヒスベルクの橋の問題・ケプラー予想・ポアンカレ予想（形の難問）：グラフ・コンピューター証明・形の研究でつながる難問です。

ほかの解かれた難問・決着した問題

• 三大作図問題とは（不可能・決められないと証明）
  定規とコンパスだけで、円と同じ面積の正方形・体積2倍の立方体・角の三等分を作図できるか。どれも不可能と証明された
• 平行線公準の問題とは（不可能・決められないと証明）
  ほかの公理から平行線の公理を証明できるか。証明できず、成り立たない幾何学（非ユークリッド幾何学）もあると分かった
• 5次方程式の解の公式とは（不可能・決められないと証明）
  2次・3次・4次方程式のような、四則と累乗根だけの解の公式が5次方程式にもあるか。一般にはないと証明された
• ケプラー予想とは（解決）
  同じ大きさの球をいちばん密に詰める方法は、八百屋のみかんの積み方か。コンピューターで証明
• ケーニヒスベルクの橋の問題とは（解決）
  7つの橋を1回ずつ渡って元にもどれるか。できないと示し、グラフ理論が生まれた
• 連続体仮説とは（不可能・決められないと証明）
  自然数と実数の「あいだの大きさ」の無限はあるか。今の集合論の公理からは決められないと証明された
• ポアンカレ予想とは（解決）
  穴のない3次元の図形は、球と同じ形と言えるか。ミレニアム懸賞問題で唯一の解決
• ABC予想とは（解決と発表・評価が分かれる）
  a＋b＝c のとき、c は abc の素因数の積よりめったに大きくならない。望月新一の証明は2021年に論文掲載、評価が分かれている

← 前の時代：双子素数予想とは（未解決）　｜　次の時代：リーマン予想とは（未解決） →

数学の難問・未解決問題の一覧（いつ・だれが解いたか）　｜　有名な数学者一覧

読みもの（合格大作戦の数学の記事）

• 算数・数学の公式一覧（公式辞典）
  公式・証明・例題を1つずつ
• 数学用語辞典（用語の意味を1語1ページ）
  素数・漸近線など200語
• 数学オリンピックの問題（長方形に詰めた正方形）
  中学生でも解ける本番の問題
• 数学の勉強法（解法の暗記→演習→過去問）
  青・黄・赤チャートの使い分け
• 京大理系数学の出題分析（1999〜2026年度）
  大問別一覧と頻出分野ランキング
• フェルマーの最終定理とは？わかりやすく解説
  n＝2と3以上の違い、ワイルズの証明

よくある質問

あわせて読みたい

• 数学の難問・未解決問題の一覧
• 有名な数学者一覧
• 算数・数学の公式一覧（公式辞典）