「四色定理の驚くほど簡単な証明」が間違っている理由

先週投稿した「四色定理の驚くほど簡単な証明」のどこが間違っているのか説明したいと思います。

前回紹介した「驚くべき証明」は次のようなものでした。

  1. 5つの国だけからなる地図は4色で塗りわけることができる。
  2. 地図の外周(実際の地図で言うと海に面している部分)にある国は3色で塗りわけることができる。
  3. いま国の数が n の地図は4色で塗り分けられると仮定し、その外周に国を一つ追加し、n+1 個の国からなる地図を作ることを考える。2. より元の地図の外周で使われていない色があるはずである。その色で追加した国を塗れば、n+1個の国全体が4色で塗り分けられる。
  4. 1. の5つの国からスタートして 3. の手順を繰り返せば任意の大きさの地図を4色で塗りつぶすことができる。(証明終わり)

どこが間違っているかを説明する前に、一つ確認しておくことがあります。

一般に、ある命題を証明しようとするときに、その命題自体を証明の中で使ってはいけません。当たり前すぎて、わざわざ何を言っているのかと思われるかもしれませんが、「証明しようとする命題」の見た目が変わってしまうと、気づかないうちにそれを証明で使ってしまうことがあります。上記の「驚くべき証明」に関して言うと、1〜4の各ステップは四色定理を使わずに正しいことが示せないといけません。では、実際に一つずつ確認してみましょう。

ステップ1: 5つの国だけからなる地図は4色で塗りわけることができる

まず最初のステップは “Only five neighbors” という定理を使うことで証明できます。

“Only five neighbors” theorem
どんな地図にも隣接国が5つ以下の国が必ず一つある

この定理は四色定理を使わずに、平面的グラフにおけるオイラーの公式から導くことができます。(詳細は末尾記載の参考文献の39ページを御覧ください。)

いま5つの国だけからなる地図を考えると、そのような地図には “Only five neighbors” 定理により、隣接国を2〜4個持つ国(仮にXと呼びます)が必ずあるはずです。(いま地図全体で5国しかないので、隣接国を5個持つ国はありません。)Xの隣接国の数に応じてわけて証明します。

Xの隣接国が2個あるいは3個の場合

この場合、まずXを取り除いた4国を4色で塗り分けます。(これは必ずできます。)その後、Xの隣接国を塗るのに使われていない色でXを塗ります。これで計4色で地図全体を塗り分けることができました。

Xの隣接国が4個の場合

この場合、先ほどと同じ手は使えませんが、全部で5個しか国がないので以下の図のような状況しかありえません。

4ct-1-clipped

そうすると図の右側のように3色あれば塗り分けられることができるので、当然4色で十分ということになります。

ステップ2:地図の外周にある国は3色で塗りわけることができる

このステップは2つの場合にわけて証明します。

外周にある国が全て一度だけ外周に触れる場合

まず、下記の図のように内陸部を互いに異なる国々がぐるっと囲んでいる場合を考えます。

ct4-2-1

この場合は外周にある国の数が偶数の場合は左側のように2色、奇数の場合は3色で塗り分けることができます。

外周にある国が2回以上外周に触れる場合

言葉だとわかりにくいですが、要は内陸部を抜けて連続しない海岸部を持つような国がある場合です。この場合、先ほどの例のように交互に色を塗っていくことができない可能性があります。(下図の一番左)

ct4-2-2

証明は外周にある国の数についての帰納法でおこないます。

まず 外周にある国の数が n の地図は3色で外周が塗り分けられると仮定します。次に外周に n+1個の国があり、そのうち少なくとも1つの国は不連続な海岸線を持つとします。(下記の例で言うと、点線で囲まれた国が不連続な海岸線を持っています。)この場合、不連続な海岸線を持つ国で地図を2つに分割します。(下図の中央)すると分割された地図はそれぞれ、外周にある国の数が n 以下になるので、それぞれ3色で外周を塗り分けることができます。最後に(必要であれば色を入れ替えて)分割した地図を重ね合わせると元の地図に戻り、かつ外周は3色で塗り分けられています。

これでステップ2も証明することができました。

ステップ3: n国の地図が4色で塗れるならn+1国も4色で塗れる

さて、いよいよ佳境です。最初の2つのステップに間違いはありませんでした。となると残り2つのステップのいずれかに間違いがあるはずです。

慎重を期すためにもう一度ステップ3の説明を見直してみましょう。(説明のために一文ごと分けます。)

  • いま国の数が n の地図は4色で塗り分けられると仮定し、その外周に国を一つ追加し、n+1 個の国からなる地図を作ることを考える。
  • 2. より元の地図の外周で使われていない色があるはずである。
  • その色で追加した国を塗れば、n+1個の国全体が4色で塗り分けられる。

最初の文は単に仮定を述べているだけで、特に間違ったことは言っていません。問題は次の部分です。

「(ステップ)2より元の地図の外周で使われていない色があるはずである。」

これは一見、ステップ2で証明したことをそのまま使っているように見えますが、そうではありません。もう一度ステップ2で証明したことを確認します。

「ステップ2:地図の外周にある国は3色で塗りわけることができる。」

先ほどのステップ2の証明を思い出して欲しいのですが、そこでは外周以外の国の塗り方については一切考えていませんでした。そのことはステップ2の証明としてはまったく問題ありません。というのもステップ2は地図の外周以外の塗りわけかたについては何も述べていないからです。別の言い方をすると、ステップ2は外周以外の塗り分けに何の条件もない前提で、外周の塗り分けは3色あればできる、と述べているにすぎません。

ところが、ステップ3の「証明」に必要とされるのは

n国全体を4色でかつ外周は3色で塗り分ける方法がある」(※)

ということです。これはステップ2が証明したこととは異なります。「驚くべき証明」の間違いはここにあります。

間違いに気づきにくい理由

私自身はこの間違いに気づくのに大分時間がかかりました。大きな理由は、ステップ3の証明が本当に必要とすること、つまり(※)が真であり、かつ、見かけ上ステップ2で証明したことに非常に似ていたからです。

実際(※)は四色定理を用いれば次のように簡単に証明できます。

ct4-true2

ある地図があったとき(上図左)、全ての国を囲むように新しい国を追加した地図を考えます。(図右。黄色に塗られた国が追加した国。)四色定理を用いると右の地図は4色で塗り分けることができます。したがって、元の左の地図で外周にあたる国々はどれも追加した国に触れているので、その国の色(黄色)以外で塗られていないといけません。その塗り分けを保ったまま追加した国を取り除けば、外周は3色かつ全体は4色で塗り分けられた地図を得ることができます。

私は「驚くべき証明」を読んだあと、「全体が4色で塗れるからと言って外周が3色で塗れるとは限らないぞ」と疑いだしたのですが、反例が作れずしばらず行き詰まっていました。あるところで、四色定理が成り立つ以上そもそも反例が作れるはずはないことに気づいたので、反例探しをやめることができましたが、もし四色定理が成り立つことを知らなかったらばそのまま反例探しを続けていたかもしれません。反例は証明を反駁するのにとても有効な手段ですが、常に使えるものではない、という良いレッスンになりました。

参考文献

前回の記事でも紹介しましたが “Four Colors Suffice” という本は四色定理をめぐる歴史も含め、とてもわかりやすく説明しています。邦訳も出ています。(ただ原著のカラフルな図が再現されているかは分かりません。)数学好きの方には大変おすすめです。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中