四色定理

四色定理（よんしょくていり／ししょくていり、英: Four color theorem）とは、厳密ではないが日常的な直感で説明すると「平面上のいかなる地図も、隣接する領域が異なる色になるように塗り分けるには4色あれば十分だ」という定理である。

4色に塗り分けられている（常にさらに外側の領域を想定することで、地図の外縁部は3色で塗り分け可能で、球面においても四色定理が成立することがわかる）

概説

これを「地図の塗り分け」とすると、例えば飛び地を所属地と常に同じ色にしなければならない、とした場合、何色あっても足りない、といった問題などがあるので、まず、日常的な直感から離れた表現で記述し直すと「境界線によって囲まれたいくつかの領域からなる平面図形があり、境界線の一部を共有する（隣り合った）領域は異なった色で塗らなければならない、としたとき、4色あれば十分である」となる。

グラフ理論でとらえると、

「平面グラフは4彩色可能である」

という定理になる（後述）。

なお、境界線ではなく、点のみを共有する領域は隣り合っているものとはみなされず、互いに同色で塗ってもよい（飛び地の場合と同じく、この条件なしではやはり何色あっても足りなくなる。現実の地図では稀だが、有名なものでは米国に、1点に4州が接する「フォー・コーナーズ」という地点がある）。また平面だけでなく、球面の場合も同様である（平面の地図に、全周囲となる領域を加え、それを反対側の1点に集めるようにして球にすればよい。逆も同様）。しかし、ドーナツや「繋がったドーナツ」のような、穴がある形状の表面については同様とはいかない（これも後述）。

証明される前は四色問題と呼ばれることもあり、1975年に証明されたのだが、未証明の期間が長かったため現在でも四色問題と呼ばれることがある。

3つの境界線が1点に集まっている場所があるため、3色必要であることはただちに明らかである。続いて、ある領域の周囲にいくつかの領域がある場合（日本地図では長野県のような場合）を考える。周囲の領域の個数が偶数であれば3色で塗り分けできるが（長野県の場合はそうなる^{[注 1]}）、奇数個の領域で囲まれている場合は3色での塗り分けは不可能で、どうしても4色が必要である。そして、4色あればどんな場合でも塗り分け可能なのか？　ということが問題である。

前述のように、グラフ理論により「平面グラフは4彩色可能である」という定理となる（証明もグラフ理論によってなされている）。参考例を図に示すが、まず、地図の境界線をグラフの辺、境界線が接続する点をグラフの頂点としたグラフを作る。その双対グラフにおける頂点の彩色が、元の地図の塗分けと同じ問題となる。

 

また、このような領域の塗り分けが有限の色数で必ず可能となるのは平面（二次元）以下の次元までであり、三次元以上では領域の取り方次第でいくらでも色数が必要な例が作れる。

歴史

 

（海や他国領土の色を除いて）4色に塗り分けられたアメリカ合衆国の州

1852年に法科学生のフランシス・ガスリーが数学専攻である弟の(フレデリック・ガスリー)（英語版）に質問したのを発端に問題として定式化され、19世紀後半になって数学者がその話を聞いて証明を試みたが、多くの数学者の挑戦をはねのけ続けていた。

1879年、(アルフレッド・ケンプ)（英語版）による証明が『(アメリカ数学ジャーナル)』誌上で発表された。この証明は妥当と見なされていたが、1890年になって(パーシー・ヒーウッド)（英語版）により不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。これは五色定理と呼ばれている。4色で十分かどうかは、グラフ理論における最も有名な未解決問題として残った。

1976年に(ケネス・アッペル)（英語版）とヴォルフガング・ハーケンは、(ハインリヒ・ヘーシュ)（英語版）により考案された「(放電法)（英語版）」と呼ばれる手続きを改良し、コンピュータを利用して約2000個の（後に1400個あまりに整理された）可約な配置からなる不可避集合を見出し、四色定理を「証明」するに至った^[1][2][3]。

これは一応は認められたが、人手による実行が（事実上）不可能なほどの複雑なプログラムの実行によるものであることから、ハードウェアやソフトウェア（コンピュータやそのプログラム）のバグの可能性などの懸念から、その確実さについて疑問視する向きもあった。

しかしその後、1996年に(ニール・ロバートソン)（英語版）らによりアルゴリズムやプログラムの改良が行われ、より簡易な手法（従来の放電手続きよりシンプルな放電手続きを考案し、不可避集合の数を1405個から633個に抑えた）による再証明が行われる^[4]など、第三者による複数の改良された証明が行われ、証明は確実視されるようになっていった。2004年には(ジョルジュ・ゴンティエ)（英語版）が定理証明系Coqを用いて、よりシンプルな証明を行うなど^[5]、コンピュータの応用手法の洗練により、より確かな手続きで証明が行われるなどしているため、現在では四色問題は解決していると捉えられている。

証明

四色定理の証明法は次の2段階に分けられる。

1. どのような平面グラフをとってきても、その集合に属するグラフのどれか一つが部分グラフとして含まれるグラフの集合を考える。このような性質をもつグラフの集合を不可避集合という。
2. 不可避集合をうまく選ぶと、それに属するどのグラフも次の意味で可約にできる。すなわち、その部分グラフを含むグラフがあったとき、その部分グラフを除いたものが4色で塗り分けが可能ならば、グラフ全体も4色で塗り分けができる。

実際、もしも塗り分けに5色以上が必要な四色問題の反例となるグラフがあったとしたならば、その中で頂点の個数が最小のものを考える。すると、1.よりこのグラフは不可避集合に属する部分グラフを含む。2.により、この部分グラフを除いた、より頂点数の少ないグラフが既に四色問題の反例を与えることになる。しかし、それは最小の反例をとってきたという仮定に反する。

アッペルとハーケンはコンピュータによる実験を繰り返し、プログラムを何度も書き換えながら、可約なグラフから成る約2,000個のグラフからなる不可避集合を求めた。当時の大型汎用コンピュータであるIBM System/370^{[注 2]}を1,200時間以上使用したといわれている。

複雑に思える問題に対して簡潔にまとまった比較的短い証明（解答）を、エレガントな証明（解答）と言うことがある。四色定理に対するある種「力業による証明」は、これとは対極にあるものとして揶揄を込めて「エレファント（象）」な証明とも言われた。5色による塗り分けが可能であることの証明が簡潔なものであるのとは対照的である。

その後アルゴリズムは改良されたが、現在でもコンピュータを利用しないで済ませられる証明は得られていない。それどころか完全に自然言語を離れて、プログラムにバグがないことも含めた四色定理の証明全体をコンピュータ上の証明検証系システム（ソフトウェア）Coqによってチェックさせた仕事がある。またコンピュータを使うこと以上に、証明の構成法自体が四色定理の解決のために特化していて、他の問題との関係性に乏しいことも数学者の間で人気のない理由になっている。

　現に、東京女子大の小西善二郎講師は、元のIBM System/370は現在入手不可能だが、等価回路で元のアセンブラによるプログラムの欠陥がないとは言えない、としている。

一般化

一般に種数 g ≥ 0 の閉曲面（わかりやすく言えば、穴が g 個あるドーナツ）を塗り分けるのに最低限必要な色の数は、1890年にヒーウッドによって

${\displaystyle \left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor }$ （${\displaystyle \lfloor \cdot \rfloor }$ はフロア関数）

と予想された。この予測が g ≥ 1 に対して正しいことは、リンゲルとヤングスにより1968年に証明された^[6]。この式に形式的に平面の場合である g = 0 を代入すれば、4 となる（ただしこれをもって四色問題の証明とすることはできない）。

トーラス（円環、いわゆるドーナツの形、g=1の場合）上のグラフは、7色で彩色可能である。

   

3彩色問題

「与えられた地図Gに対し、Gを3色で塗り分けできるかどうかを決定せよ」という問題を3彩色問題という。四色問題のときと同じく隣り合う土地を同じ色で塗ってはならない。

3彩色問題はNP完全問題の一つであることが知られている。

四色問題とジョーク

解決される少し前の1975年に一つのハプニングがあった。数学パズル（en:Recreational mathematics）で有名なマーティン・ガードナーが『サイエンティフィック・アメリカン』の連載コラム「Mathematical Games」において、これが四色問題の反例であるという（五色が必要だと主張する）境界の図を載せたのである^[7][8][9]。

「なぜか世間の注意をひかなかった6つの衝撃の発見」と題する4月号のこの記事は、実のところエイプリルフールの冗談であり、他の内容もやはりラマヌジャンの定数（(ほとんど整数#ラマヌジャンの定数)を参照）など、一見びっくりする数学ジョークというものであった。そして「四色問題の反例」は、実はマクレガーによる数学パズル問題で、四色での塗り分けは一見不可能に見えるが、実際に塗り分けを試みればあまり難航することもなく解ける（かもしれない^{[注 3]}）というものである。そのため、塗り分けができたぞという手紙が千通以上も寄せられることになったという^[9][10]。

脚注

注釈

1. ^ 新潟県・群馬県・埼玉県・山梨県・静岡県・愛知県・岐阜県・富山県 の8県。
2. ^ 「最高速のスーパコンピュータ」などと書かれていることがあるが、同機はいわゆる（クレイなどの）「スーパーコンピュータ」ではない。大成功を収めた1964年発表のSystem/360（360度さまざまな業務に対応できる意）に続く、1970年発表の後継機であり、1975年当時のIBMの主力機である。System/360同様System/370ファミリを形成しており、モデルによって性能に幅がある。
3. ^ ある程度は、解く者の試行錯誤が要求され、運の要素もある。

出典

1. ^ K. Appel, W. Haken, "Every planar map is four colorable" (Bulletin of the American Mathematical Society Volume 82, Number 5, September 1976)
2. ^ "Every planar map is four colorable. Part II: Reducibility" by K. Appel, W. Haken, and J. Koch (Illinois J. Math. Volume 21, Issue 3 (1977), 491–567.)
3. ^ Contemporary mathematics 98 "Every Planar Map is Four Colorable" by Kenneth Appel and Wolfgang Haken
4. ^ "A new proof of the four-colour theorem" by Neil Robertson, Damiel P. Sanders, Paul Seymour, and Robin Thomas (Electronic Research Announcements of the American Mathematical Society Volume 2, Number 1, August 1996)
5. ^ "A computer-checked proof of the Four Colour Theorem" by Georges Gonthier (Microsoft Research Cambridge) http://www2.tcs.ifi.lmu.de/~abel/lehre/WS07-08/CAFR/4colproof.pdf
6. ^ Weisstein, Eric W. "Map Coloring". MathWorld (英語).
7. ^ ガードナー & 一松 (1977)
8. ^ 高木 (1976, XIV 最近の話題/パズルの最前線)によると、日本版『サイエンス』誌6月号に掲載、と見える。
9. ^ ^{a b} 一松 (1978, pp. 197–204)
10. ^ Weisstein, Eric W. "McGregor Map". MathWorld (英語). このページでその問題が見られるが、解答（ネタバレ、spoiler）もすぐ隣にあるので、パズルとして楽しみたい場合は他を探すこと。

参考文献

• アッペル、ハーケン、島内剛一 訳「4色問題の解決」『サイエンス』1977年12月号、日経サイエンス、1977年12月、18-29頁。 
• (Wilson, Robin); Stewart, Ian (2013-11-10), Four Colors Suffice: How the Map Problem Was Solved, Princeton Science Library (Revised Color ed.), Princeton University Press, ISBN (978-0-691-15822-8), http://press.princeton.edu/titles/10116.html  - 改訂多色版。イアン・スチュワートによる前書を追加。
  • ウィルソン, ロビン『四色問題』茂木健一郎 訳、新潮社、2004年11月30日。ISBN (978-4-10-545201-8)。 
  • ウィルソン, ロビン『四色問題』茂木健一郎 訳、新潮社〈新潮文庫 Science＆History Collection〉、2013年12月1日。ISBN (978-4-10-218461-5)。http://www.shinchosha.co.jp/book/218461/。  - 原著初版の翻訳。
• ガードナー, マーティン「数学ゲーム」『サイエンス』1975年6月号、日経サイエンス、1975年6月。 
• ガードナー, マーティン『ガードナーの新・数学娯楽 球を詰め込む・4色定理・差分法』(岩沢宏和)・(上原隆平) 監訳、日本評論社、2016年4月20日、162-180頁。ISBN (978-4-535-60423-0)。 
• 島内剛一「四色問題」『数学セミナー』1977年2月～9月号、日本評論社、1977-02～09。 
• 高木茂男『数学遊園地 数のもつ不思議さを楽しもう』講談社〈ブルーバックス B-291〉、1976年。ISBN (978-4-06-117891-5)。 
• 一松信『四色問題 その誕生から解決まで』講談社〈ブルーバックス B-351〉、1978年4月25日。ISBN (4-06-117951-9)。 
  • 一松信『四色問題 どう解かれ何をもたらしたのか』講談社〈ブルーバックス B-1969〉、2016年5月29日。ISBN (978-4-06-257969-8)。https://bookclub.kodansha.co.jp/product?item=0000194930。 
• 広瀬健「四色問題と電子計算機」『bit』1977年7月～10月号、共立出版、1977-07～10。 

関連項目

• グラフ彩色
• グラフ理論
• 五色定理
• トーラス

外部リンク

 

ウィキメディア・コモンズには、四色定理に関連するカテゴリがあります。

• 『(四色問題)』 - コトバンク
• 『四色定理の紹介と五色定理の証明』 - 高校数学の美しい物語
• THE FOUR COLOUR THEOREM - Robertsonらによる実際の633個の可約な不可避配置集合を見ることができる。双対グラフ表記のため、国が頂点、国境が枝で表される。最初の配置は(バーコフのダイヤモンド)であり、黒丸が5枝点を表す。以下、無印が6枝点、白丸が7枝点、四角が8枝点、三角が9枝点、五角形が10枝点で、最後の無印のみが11枝点となっている。
• 改良されたアルゴリズム （英語）
• Weisstein, Eric W. "Four-Color Theorem". MathWorld (英語). -（四色定理）
• Weisstein, Eric W. "Map Coloring". MathWorld (英語). -（地図の塗り分け）
• Weisstein, Eric W. "Torus Coloring". MathWorld (英語). -（トーラスの塗り分け）