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

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

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

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

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

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

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

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

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

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

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

Xの隣接国が２個あるいは３個の場合

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

Xの隣接国が４個の場合

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

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

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

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

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

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

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

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

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

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

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

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

ステップ３： ｎ国の地図が４色で塗れるならｎ＋１国も４色で塗れる

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

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

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

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

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

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

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

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

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

「ｎ国全体を４色でかつ外周は３色で塗り分ける方法がある」（※）

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

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

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

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

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

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

参考文献

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