しいたげられたしいたけ

空気を読まない。他人に空気を読むことを要求しない

ロビン・ウィルソン、茂木健一郎(訳)『四色問題』(新潮社)

四色問題

四色問題

四色問題
四色あれば、どんな地図でも
隣り合う国々が違う色になるように
塗り分けることができるのか?

(p12)
四色問題または四色定理とは、十九世紀半ばの問題提示から1972年の証明の完成まで百年以上を要した数学の有名な難問だが、その解決には微積複素数群論も必要とせずシロウトでも十分楽しめる。しかし「論理をきっちりと積み上げていく」ことを要求される点は、やはり数学なのである。そのアプローチの概略は以下の通り。
まず、地図をすべての交点で三か国だけが接する「三枝地図」(さんしちず)に置き換える(もし交点で四か国以上が接している箇所があれば、そこに架空の国を置いて、塗り分けたのち架空の国を取り除けばよい)。
「三枝地図」の面と境界線と交点を数え上げることにより、次の公式を得る
4C2+3C3+2C4+C5-C6-2C7-3C8…=12(p75)
ここにCnはn本の境界線で他の国と接する国の数である。
Cnはマイナスの値を取る事はないから、下記の重要な定理が得られる。

どんな地図にも、五個以下の隣国しか持たない国が
少なくとも一つ含まれる

(p70)
そして、もし四色定理が間違っていて塗り分けに五色以上を必要とする地図があったとすれば、という仮定を用いて、背理法により四色定理を証明しようというのだ。もし塗り分けに五色以上が必要な地図があるとするならば、そこに描かれている国の数には最小値があるはずである。これを「最小反例」と呼ぶ(p87)。
まず「最小反例」には、二か国しか隣国を持たない国と三か国しか隣国を持たない国は含まれない(すなわちC2=C3=0)。なぜならこれらの国は、塗り分けを工夫することにより他の国に影響を与えず四色で塗りなおすことができることがすぐに示せるからだ(詳細はp88〜89)。
次に「最小反例」に四か国しか隣国を持たない国が含まれない(C4=0)ことも、少し難しくはなるが証明できる(p100〜101)。
そして五か国しか隣国を持たない国が「最小反例」に含まれないことを証明できれば、C5=0となり上記の公式と矛盾を生じるため、背理法による四色定理の証明が完成する。
しかしこのアプローチは、まさにその最後に残された五か国しか隣国を持たない国を扱おうとしたときに、決定的な困難に直面するのである…
追記:(9/13)
いらんことを書くと、ブルーバックスに一松信『四色問題―その誕生から解決まで (ブルーバックス 351)』というのがあって、「ケンプ環」「バーコフのダイヤモンド」「放電法」など取り上げられている主な話題はロビン・ウィルソン本とほぼ同じなのだが、残念なことにこちらは品切れ。