四色問題（四色定理）は平面上のいかなる地図も四色あれば隣合う国が同色にならないように塗り分けることができるというものです。
筆者は NHK の番組「笑わない数学」で解説されていたのを視聴し興味を持ちました。
ただ番組を見ても１つだけどうしても理解できなかったことがありました。
それは「なぜ６辺国以上の国を考慮しなくて良いのか」ということです。
Web を検索してもぱっと分かる解説がヒットせず、最終的には同僚に教えてもらいました。
本記事では四色問題について「なぜ６辺国以上の国を考慮しなくて良いのか」について同僚に教えてもらって納得した感覚的に分かる方法について記します。
※NHK 公式でも６辺国以上の国の扱いついて説明してくれていることに後日気づきました。そちらもご覧下さい。
前提知識
四色問題について考える際に必要な前提知識についておさらいしておきます。
前提１. 地図は平面グラフに置き換えられる
四色問題で扱う地図は点と点同士を繋げる辺で表現できます。
前提２. いかなる地図も５辺国以下の国が含まれる
２つの辺がある国を２辺国、３辺なら３辺国、といったように言います。
いかなる地図も５辺国以下の国が存在することがオイラーの多面体定理を使うことで証明でき、四色問題の証明でもこの考えが使われます。
※ここではなぜ５辺国以下の国が存在することが証明できるかは省略します。YouTube で解説している動画もあるようでしたのでそういったものを参考にしてみてください。
前提３． ５辺国以下の国は四色あれば塗り分けできることが証明済み
５辺国以下の国はどんなパターンであっても四色あれば塗り分けられることが証明済みです。
４辺国以下は人の想像の範囲内でも考えられるため簡単なのですが５辺国はパターンがかなりあるため人のチカラだけで考えることはかなり困難です。そのためコンピュータのチカラを借りることで全パターン塗り分け可能と判明したそうです。
この点について人によってはモヤっとするかもしれませんが筆者は「そういうもの」として考えることにしました。
「数学的帰納法」を使って証明する
さて、前提知識をおさらいしたところで本編に入っていきます。
四色問題は数学的帰納法（番組の言葉を借りると「OK リレー作戦」）を使うことで証明できるそうです。
これは四色で塗り分けたい地図 A（国の数 n の地図）について、１つ国を減らした地図 B（国の数 n-1 の地図）が四色に塗り分けられているとするならば地図 A は四色で塗り分けられる、といったものです。
ここで私はつまづきました。
- 数学的帰納法を使う際になぜ６辺国以上の国のことを考えなくていいのか？
ということです。
これについて図を使って説明します。
今回は７辺国のある以下の地図 A を使って説明します。
この国は前提１より以下の平面グラフで表すことが出来ます。
そしてこの地図 A は前提２より５辺国以下の国が存在します。
ここから１つ国を減らした地図 B を作成します。ここで減らす国は５辺国以下の国です。（ここが同僚に説明してもらうまで分かっていなかったポイントでした）
試しに適当な５辺国以下の国アを１つ減らしてみましょう。
仮にこの１つ減らした地図 B が四色に塗り分けられているとして、ここに先ほど減らした国アを追加したとします。
このとき、国アは５辺国以下のため前提３より必ず四色への塗り分けが成功します。
いやいや、「仮に１つ減らした地図 B が四色に塗り分けられている場合でしょ？」と思いますよね。あくまで仮なんだからそれを仮じゃないようにしないといけません。しかしそこは一旦置いておきもう少しこのやり方を続けてみましょう。
１つ減らした地図 B も前提２より５辺国以下の国が存在します。ということで次の５辺国以下である国イを減らした地図 C を作ってみましょう。
国イを減らした結果、なんとこの地図 C から６辺国以上の国はなくなり、全て５辺国以下の国となりました。この「２つの国を減らした地図 C」は５辺国以下の国しか存在しないため前提３より四色で塗り分けられます。
これはつまり「仮に１つ（２つ）減らした地図が四色に塗り分けられている」が「仮」ではなく「絶対に四色に塗り分けられている」状態になります。
そしてこの地図 C から減らした国イと国アを逆順に追加して戻していきます。このとき国イ国アのどちらも５辺国以下ですので追加しても四色に塗り分けられますよね？つまり元の地図 A は四色で塗り分けられることがこれで説明できました。
この考え方、まとめますと以下の通りです。
- 地図から５辺国以下の国を１つずつ取り除き最終的に５辺国以下の国しかない地図を作る
- ５辺国以下しかない地図に対して前提３を使って四色で塗り分ける
- 取り除いていった国を逆順で追加＆塗をしていけば四色に塗り分けられた地図が完成
この考え方により、６辺国以上ある地図も結局は５辺国以下のことだけ考えれば良いということになりました。めでたしめでたし。
余談：この考え方で四色問題を解くプログラムが書けるかもしれませんね。世の中に既に存在する四色問題を解くプログラムのアルゴリズムは転がってそうなのでそちらも気になります。
おしまい
以上で説明は終わりになります。
おそらく数学的帰納法の考え方に慣れている人であれば番組中の説明だけですっと分かったのかもしれませんね。
本記事が四色問題の理解で私のようにつまづいてしまった人の助けになれば幸いです。