以前のブログで説明がなかなか納得されない例として四色定理を取り上げましたが、実際にどこが納得しがたいのか知りたいと思い勉強してみることにしました。とはいえ、原論文をいきなり読むのはハードルが高すぎるので “Four Colors Suffice: How the Map Problem Was Solved” を読むことから始めました。（この本はカラーの図版も美しく、四色定理をめぐる歴史も丁寧に説明しているので大変おすすめです。”四色問題”というタイトルで翻訳も出ているようです。）
完全に理解できているわけではありませんが、物議を醸した最初の証明（ちなみにココとココで論文が無料で見れます）は次の２段階から構成されていたようです。
- 平面上の地図が必ず一つは含むパターンを列挙する
- 地図からそのパターンを取り除いてできる地図が４色で塗れるならば、元の地図も４色で塗れることを示す
第一段階目で見つけたパターンがこの論文の最後に並べ立てられていますが、76ページの論文のうち62 ページを占めています。これは素人目にも数学の証明というより力押しと感じる量です。しかも著者自身が、実際にはこれよりも少ない数でも足りるかもしれない、つまり、このリストについて第二段階を実行すれば四色定理は証明できるけれども、もっと短いリストを使ってもできるかもしれない、と明言しています。（実際、もっとも短いリストが後年別の研究者により発表されています。）さらに第二段階はいくつかのヒューリスティクスの組合せをコンピュータに虱潰しに実行させることで証明しています。
驚くべき証明
流石にこれは「なんだかなぁ」という感じるのは素人だけではなく、本職の数学者も同じようです。たまたまこんな論文を見つけました。
Hemanta K. Baruah “A NON-ALGORITHMIC PROOF OF THE FOUR COLOR CONJECTURE“
概要の “We claim that this is the proper mathematical proof of the four color conjecture, for which the world of mathematics had been waiting for nearly one hundred and sixty years.” という文からも、著者の「こういうのを証明って言うんだ！」という意気込みが感じられます。
驚くべきことにこの論文はたった８ページで、しかもその証明を理解するのにはなんら高度な数学の知識は必要ありません。簡単にここに紹介したいと思います。
- ５つの国だけからなる地図は４色で塗りわけることができる。
- 地図の外周（実際の地図で言うと海に面している部分）にある国は３色で塗りわけることができる。
- いま国の数が n の地図は４色で塗り分けられると仮定し、その外周に国を一つ追加し、n+1 個の国からなる地図を作ることを考える。2. より元の地図の外周で使われていない色があるはずである。その色で追加した国を塗れば、n+1個の国全体が４色で塗り分けられる。
- 1. の５つの国からスタートして 3. の手順を繰り返せば任意の大きさの地図を４色で塗りつぶすことができる。（証明終わり）
なんというシンプルさ！こんな簡単な証明がつい最近まで気づかれずにいたというのはまったく驚きです。
落とし穴はどこにある？
… というような話では残念ながらなく、この「証明」には間違いがあります。1. と 2. は正しそうです。4. は単に帰納法を適用しただけなのでそこに間違いがあるとも考えにくいです。さて、どこに落とし穴があるのでしょうか？（ちなみ四色定理が成立するので、反例をあげて反証するという手は使えません。証明の論理に穴があります。）
CTRL+x CTRL+s 
「任意の大きさの地図を４色で塗りつぶすことができる。」
からといって
「任意の地図を4色で塗り分けられる」
とは限らない。ですかね？
いいねいいね
そこは問題ないはずです。（少なくとも数学的帰納法を認める数学者にとっては）
いいねいいね
いかなる地図であっても5国の状態から3.の手順を繰り返すことで作ることが出来るかどうかは分からないのでは？
いいねいいね
どんな地図でも外側から一つずつ国を取り除いていけば、いずれ国の数は５つまで減ります。（４カ国以下の地図が４色で塗り分けられるのは自明なので除外してます。）取り除いたのと逆の順番に国を足していけば元の地図が復元できるので、３の手順で元の地図まで辿り着くことができます。
いいねいいね
3.の時点でn＋1個の図形は四色で塗り分けられても、外側が四色になる可能性があるので次のn＋2の図形のときに外側を使われていない色で塗ると五色になってしまう可能性が出てくるのでってことですかね？
いいねいいね
n+1個のときの配色を忘れて、n+2個をあらためて塗り直せば 2. より外周を3色で塗ることができます。
いいねいいね
外周は3色で塗り分けられるかもしれませんが、その場合内部の国は２つ以上になるので、その２つの国も含めて4色で塗り分けると言えないのでは？
いいねいいね
五つの国が、必ず四色でわけられるならば、無数の国の中でどの五つの国を取り出しても、四色で分けられるのでは無いでしょうか？
間違っていたら、それについて教えて下さい。
いいねいいね
いえ、何も間違っていません。四色定理が成り立つ以上、どの5つ（というか何個でも）国を取り出しても4色で塗ることができます。
いいねいいね
全体を四色で塗り分けられることと外周が三色で塗り分けられかつ全体が四色で塗り分けられることは別ですよね。
なので普通に帰納法が回ってないと思います。
いいねいいね
>>四色定理が成り立つ以上、どの5つ（というか何個でも）国を取り出しても4色で塗ることができます
これから証明しようとしていることを、証明の途中に使うことができるならば、どんな命題でも真ですな。
いいねいいね
ステップ3の手続きに現れる地図の外周は必ずしも3色のみで塗り分けられていない。だから帰納法は機能しない。
こんな杜撰な「論文」を公表している人がいるなんてビックリ…
いいねいいね
やっぱそうだよね。
証明がシンプルだけに穴もシンプルだ。
いいねいいね