Minute先週投稿した「四色定理の驚くほど簡単な証明」のどこが間違っているのか説明したいと思います。前回紹介した「驚くべき証明」は次のようなものでした。5つの国だけからなる地図は4色で塗りわけることができる。地図の外周(実際の地図で言うと海に面している部分)にある国は3色で塗りわけることができる。個の国からなる地図を作ることを考える。元の地図の外周で使われていない色があるはずである。その色で追加した国を塗れば、n+1個の国全体が4色で塗り分けられる。手順を繰り返せば任意の大きさの地図を4色で塗りつぶすことができる。(証明終わり)どこが間違っているかを説明する前に、一つ確認しておくことがあります。一般に、ある命題を証明しようとするときに、その命題自体を証明の中で使ってはいけません。当たり前すぎて、わざわざ何を言っているのかと思われるかもしれませんが、「証明しようとする命題」の見た目が変わってしまうと、気づかないうちにそれを証明で使ってしまうことがあります。上記の「驚くべき証明」に関して言うと、1〜4の各ステップは四色定理を使わずに正しいことが示せないといけません。実際に一つずつ確認してみましょう。いう定理を使うことで証明できます。theoremどんな地図にも隣接国が5つ以下の国が必ず一つあるこの定理は四色定理を使わずに、平面的グラフにおけるオイラーの公式から導くことができます。(詳細は末尾記載の参考文献の39ページを御覧ください。定理により、隣接国を2〜4個持つ国(仮にXと呼びます)が必ずあるはずです。(いま地図全体で5国しかないので、隣接国を5個持つ国はありません。)Xの隣接国の数に応じてわけて証明します。Xの隣接国が2個あるいは3個の場合この場合、まずXを取り除いた4国を4色で塗り分けます。(これは必ずできます。)その後、Xの隣接国を塗るのに使われていない色でXを塗ります。これで計4色で地図全体を塗り分けることができました。Xの隣接国が4個の場合この場合、先ほどと同じ手は使えませんが、全部で5個しか国がないので以下の図のような状況しかありえません。すると図の右側のように3色あれば塗り分けられることができるので、当然4色で十分ということになります。ステップ2:地図の外周にある国は3色で塗りわけることができるこのステップは2つの場合にわけて証明します。外周にある国が全て一度だけ外周に触れる場合まず、下記の図のように内陸部を互いに異なる国々がぐるっと囲んでいる場合を考えます。この場合は外周にある国の数が偶数の場合は左側のように2色、奇数の場合は3色で塗り分けることができます。言葉だとわかりにくいですが、要は内陸部を抜けて連続しない海岸部を持つような国がある場合です。この場合、先ほどの例のように交互に色を塗っていくことができない可能性があります。(下図の一番左)証明は外周にある国の数についての帰納法でおこないます。地図は3色で外周が塗り分けられると仮定します。n+1個の国があり、そのうち少なくとも1つの国は不連続な海岸線を持つとします。(下記の例で言うと、点線で囲まれた国が不連続な海岸線を持っています。)この場合、不連続な海岸線を持つ国で地図を2つに分割します。以下になるので、それぞれ3色で外周を塗り分けることができます。最後に(必要であれば色を入れ替えて)分割した地図を重ね合わせると元の地図に戻り、かつ外周は3色で塗り分けられています。これでステップ2も証明することができました。n国の地図が4色で塗れるならn+1国も4色で塗れるさて、いよいよ佳境です。最初の2つのステップに間違いはありませんでした。なると残り2つのステップのいずれかに間違いがあるはずです。慎重を期すためにもう一度ステップ3の説明を見直してみましょう。(説明のために一文ごと分けます。個の国からなる地図を作ることを考える。元の地図の外周で使われていない色があるはずである。その色で追加した国を塗れば、n+1個の国全体が4色で塗り分けられる。最初の文は単に仮定を述べているだけで、特に間違ったことは言っていません。「(ステップ)2より元の地図の外周で使われていない色があるはずである。」これは一見、ステップ2で証明したことをそのまま使っているように見えますが、そうではありません。一度ステップ2で証明したことを確認します。「ステップ2:地図の外周にある国は3色で塗りわけることができる。先ほどのステップ2の証明を思い出して欲しいのですが、そこでは外周以外の国の塗り方については一切考えていませんでした。そのことはステップ2の証明としてはまったく問題ありません。いうのもステップ2は地図の外周以外の塗りわけかたについては何も述べていないからです。別の言い方をすると、ステップ2は外周以外の塗り分けに何の条件もない前提で、外周の塗り分けは3色あればできる、と述べているにすぎません。ところが、ステップ3の「証明」に必要とされるのは「n国全体を4色でかつ外周は3色で塗り分ける方法がある」(※)ということです。これはステップ2が証明したこととは異なります。「驚くべき証明」の間違いはここにあります。私自身はこの間違いに気づくのに大分時間がかかりました。大きな理由は、ステップ3の証明が本当に必要とすること、つまり(※)が真であり、かつ、見かけ上ステップ2で証明したことに非常に似ていたからです。実際(※)は四色定理を用いれば次のように簡単に証明できます。ある地図があったとき(上図左)、全ての国を囲むように新しい国を追加した地図を考えます。黄色に塗られた国が追加した国。)四色定理を用いると右の地図は4色で塗り分けることができます。したがって、元の左の地図で外周にあたる国々はどれも追加した国に触れているので、その国の色(黄色)以外で塗られていないといけません。その塗り分けを保ったまま追加した国を取り除けば、外周は3色かつ全体は4色で塗り分けられた地図を得ることができます。私は「驚くべき証明」を読んだあと、「全体が4色で塗れるからと言って外周が3色で塗れるとは限らないぞ」と疑いだしたのですが、反例が作れずしばらず行き詰まっていました。あるところで、四色定理が成り立つ以上そもそも反例が作れるはずはないことに気づいたので、反例探しをやめることができましたが、もし四色定理が成り立つことを知らなかったらばそのまま反例探しを続けていたかもしれません。反例は証明を反駁するのにとても有効な手段ですが、常に使えるものではない、という良いレッスンになりました。いう本は四色定理をめぐる歴史も含め、とてもわかりやすく説明しています。(ただ原著のカラフルな図が再現されているかは分かりません。)数学好きの方には大変おすすめです。ないのは何故でしょうか。証明なさいましたが、その逆が成り立たない根拠は何でしょうか。根拠を、もっとずっと詳しくお書き直し下さい。一体、何故、何も述べていない、とお考えになるのですか。AM論点先取り説は取り下げます。場合を、帰納法の出発点として、証明済みにしてもあるのですから。AM前回のコメントを訂正します。:勿論、5ヶ国なら、内部は、1~4ヶ国でした。4色彩色できますので、御発掘なさった証明は、イキ(活き)でしょう。AMあと、「簡単な証明」の候補として、以下のものが有り得るのではないでしょうか。同じ色の頂点を出来るだけ、ひとまとめにすることによって、以下の如く縮約できることを示す。エルデシュ・フェーバー・ロヴァーシュ予想定理が成り立つように。