四色定理

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

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

定理の正確な定式化

グラフ理論的に言えば、この定理はループのない平面グラフに対して次のことを述べている。平面グラフ$G$$G$に対して、その彩色数は${\displaystyle \chi ($G)\leq 4} $\chi (G)\leq 4$である。

四色定理の直観的な記述 - ﹁平面を連続した領域に分割したとき、隣接する2つの領域が同じ色を持たないように、領域は最大でも4つの色を使って着色できる﹂ - を正しく解釈する必要がある。

これを﹁地図の塗り分け﹂とすると、例えば飛び地を所属地と常に同じ色にしなければならない、とした場合、何色あっても足りない、といった問題などがある。例えば、簡略化した地図を考えてみると‥

この地図では、Aと書かれた二つの地域は同じ国に属している。もしこれらの領域に同じ色を与えたいならば、5つの色が必要になる。なぜなら、2つのA領域は一緒になって他の4つの領域に隣接し、それぞれの領域は他のすべての領域に隣接しているからである。なお別々の領域に同じ色を持たせることは、平面の外側にそれらをつなぐ'ハンドル'を追加することでモデル化できる。

このような構成によって、この問題はトーラス︵種数1の曲面︶上の地図の色付け問題と等価になる。

よってまず、日常的な直感から離れた表現で記述し直すと﹁境界線によって囲まれたいくつかの領域からなる平面図形があり、境界線の一部を共有する︵隣り合った︶領域は異なった色で塗らなければならない、としたとき、4色あれば十分である﹂となる。

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

﹁平面グラフは4彩色可能である﹂

という定理になる︵後述︶。

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

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

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

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

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

歴史

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

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

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

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

これは一応は認められたが、人手による実行が︵事実上︶不可能なほどの複雑なプログラムの実行によるものであることから、ハードウェアやソフトウェア︵コンピュータやそのプログラム︶のバグの可能性などの懸念から、その確実さについて疑問視する向きもあった。たとえば、東京女子大の小西善二郎講師は、元のSystem/370は現在入手不可能だが、等価回路で元のアセンブラによるプログラムの欠陥がないとは言えない、としている。

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

コンピュータによる証明

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

(一)どのような平面グラフをとってきても、その集合に属するグラフのどれか一つが部分グラフとして含まれるグラフの集合を考える。このような性質をもつグラフの集合を不可避集合という。

(二)不可避集合をうまく選ぶと、それに属するどのグラフも次の意味で可約にできる。すなわち、その部分グラフを含むグラフがあったとき、その部分グラフを除いたものが4色で塗り分けが可能ならば、グラフ全体も4色で塗り分けができる。

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

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

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

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

証明のアイディアの概要

以下の議論はEvery Planar Map is Four Colorable (Appel & Haken 1989)の序論に基づく要約である。欠点はあるが、ケンペの4色定理の最初の証明とされるものは、後に4色定理の証明に使われる基本的なツールの一部を提供した。ここでの説明は、上記の現代グラフ理論の定式化の観点から言い直したものである。

ケンペの議論は次のようなものである。まず，グラフで区切られた平面領域が三角分割されていない場合，つまり，境界にちょうど3つの辺がない場合，境界のない外側の領域も含めてすべての領域を三角形にするために，新しい頂点を導入することなく辺を追加することができる．この三角化グラフが4色以下で着色可能であれば，辺を削除しても同じ着色法が成り立つので，元のグラフも同様である．したがって，三角形化されたグラフの4色定理を証明するには，すべての平面グラフについて証明すれば十分であり，一般性を損なうことなくグラフが三角形化されていると仮定する．

頂点、辺、領域︵面︶の数を v, e, fとする。各領域は三角形であり、各辺は2つの領域で共有されるので、2e=3fとなる。これはオイラーの多面体定理v- e+ f= 2 を使えば、6v- 2e = 12.さて、頂点の次数とは、その頂点に接する辺の数である。v_nを次数nの頂点の数、Dを任意の頂点の最大次数とする、

$6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.$$6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.$.

しかし、12 > 0であり、すべてのi≥ 6に対して6 - i≤ 0なので、これは次数5以下の頂点が少なくとも1つあることを示している。

もし5色を必要とするグラフがあるとすれば、そのようなグラフは最小であり、どの頂点を取り除いても4色になる。このグラフをGと呼ぶ。もしd(v) ≤ 3 ならば，Gからvを取り除き，小さいグラフを4色化した後，vを再び加え，隣と異なる色を選んで4色化を拡張することができるからである．

A graph containing a Kempe chain consisting of alternating blue and red vertices

先ほどと同様に、頂点vを取り除き、残った頂点を4色に着色する。もしvの4つの隣がすべて異なる色、例えば時計回りの順序で赤、緑、青、黄であれば、赤と青の隣を結ぶ赤と青の頂点の交互のパスを探す。このような経路はケンプ鎖と呼ばれる。赤と青の隣同士を結ぶケンペ鎖があるかもしれないし，緑と黄の隣同士を結ぶケンペ鎖があるかもしれない．連鎖していないのは赤と青の隣同士だとする。赤と青の交互のパスで赤の隣の頂点に接続されているすべての頂点を探索し、これらのすべての頂点で赤と青の色を逆にする。その結果、やはり4色使いになり、vを戻して赤に着色することができる。

これで残るのは次数5の頂点がGにある場合だけであるが、ケンペの議論にはこの場合の欠陥があった。HeawoodはKempeの間違いに気付くと同時に、5色しか必要でないことを証明することで満足するのであれば、︵最小反例が6色を必要とすることだけを変えて︶上記の議論を実行し、次数5の状況でKempeの鎖を使って五色定理を証明することができることに気付いた。

いずれにせよ、この次数5の頂点のケースを扱うには、頂点を取り除くよりも複雑な概念を必要とする。むしろ、︵Gの︶各頂点の次数が指定されたGの連結部分グラフである構成を考えることに議論の形式が一般化される。例えば、次数4の頂点の状況で説明されるケースは、Gにおいて次数4であるとラベル付けされた1つの頂点からなる構成である。上記と同様に、構成を削除して残りのグラフを4色化した場合、構成を再び追加したときに4色化も拡張できるように色付けを修正できることを示せば十分である。これが可能な構成を還元可能な構成と呼ぶ．ある構成の集合のうち少なくとも1つがGのどこかに必ず出現する場合、その集合を不可避な構成と呼ぶ。上の議論は、まず5つの構成︵次数1の頂点、次数2の頂点、...、次数5の頂点︶からなる不可避的な集合を与え、最初の4つが還元可能であることを示した。

Gは三角形であり、構成中の各頂点の次数は既知であり、構成内部の辺はすべて既知であるため、与えられた構成に隣接するGの頂点の数は決まっており、それらはサイクルで結ばれる。これらの頂点は配置の環を形成する。環にk個の頂点を持つ配置はk環構成であり、環を持つ配置は環構成と呼ばれる。上記の単純な場合と同様に、リングのすべての異なる4つのカラーリングを列挙することができる。構成のカラーリングに変更することなく拡張できるカラーリングは、最初は良いと呼ばれる。例えば、3つ以下の近傍を持つ上記の単一頂点の配置は、最初は良い配置であった。一般に、リングのカラーリングを良いものに変えるためには、上の4つの近傍がある場合のように、周囲のグラフを系統的に再カラーリングする必要がある。リングの4つのカラーリングの数が多いので、これはコンピュータの支援を必要とする主要なステップである。

最後に、この手順で漸化できる構成の不可避集合を特定することが残る。このような集合を発見するために使われる主要な方法は、放電法である。放電法の根底にある直感的な考え方は、平面グラフを電気的なネットワークとして考えることである。最初に正負の﹁電荷﹂が頂点に分配され、合計が正になるようにする。

上の式を思い出してほしい‥

$\sum _{i=1}^{D}(6-i)v_{i}=12.$$\sum _{i=1}^{D}(6-i)v_{i}=12.$
各頂点には6-deg(v)の初期電荷が割り当てられる。次に、ある頂点から隣接する頂点へ、規則に従って電荷を系統的に再分配することで電荷を﹁流す﹂︵discharging procedure︶。電荷は保存されるので、一部の頂点はまだ正の電荷を持っている。規則によって正電荷を持つ頂点の配置の可能性が制限されるので、そのような配置の可能性をすべて列挙すると、避けられない集合が得られる。

やむを得ない集合の中に還元可能でないものがある限り、︵他の配置を導入しながら︶それを取り除くように放電の手順を修正する。アペルとハーケンの最終的な排出手順は非常に複雑で、結果として得られる不可避的な構成集合の説明と合わせて400ページのボリュームを満たしたが、生成された構成が還元可能であることは機械的に確認することができた。不可避的コンフィギュレーションを記述した本そのものの検証は、数年にわたる査読によって行われた。

ここでは説明しないが、証明を完成させるために必要な技術的な詳細は、はめ込み 可約性'である。

一般化

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

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

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

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

3彩色問題

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

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

四色問題とジョーク

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

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

脚注

出典

参考文献

●アッペル、ハーケン、島内剛一 訳﹁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.wolfram.com (英語). -︵四色定理︶

●Weisstein, Eric W. "Map Coloring". mathworld.wolfram.com (英語). -︵地図の塗り分け︶

●Weisstein, Eric W. "Torus Coloring". mathworld.wolfram.com (英語). -︵トーラスの塗り分け︶