解説２
平面地図の「５色定理」の証明について。面の彩色です。大まかなことの復習です。図は地図のごく一部を描いたものと思ってください。
彩色（塗分け）に６色必要な平面地図（地図の大きさも国の数も有限とします）があったと仮定して、国の数が最も小さい地図の１つを最小反例とします。
最小反例なので国境を接している隣国が４つ以下の国はないものとして構いません。平面地図なので、必ず“５辺国”があります。
５辺国の１つに６番目の色を割りつけると、他の国は５色で彩色できるはずです。その５辺国は５色の外国に隣接しています。
そこでその５辺国の国境２つを図のように取り除いて、国を合併させます。
国の数が少なくなったので、５色で彩色可能になったはずです。
国境をもとに戻すと、５辺国は４色以内の外国に囲まれている状態になります。
隣国に使われていない色を５辺国に割り当てると、地図全体が５色以内で塗分けられた状態になり、仮定に矛盾します。
ゆえに最小反例が存在するとの仮定は誤りであり、反例は存在せず、５色定理が証明できました。
この証明には次のような特徴があります。（双対グラフにして頂点を彩色するイメージに戻します。）
- より小さなグラフは５色で彩色できることが仮定され、数学的帰納法と背理法が使われる。
- グラフの構造に関しては、平面グラフで次数が５の頂点があるという以外の事柄は必要がない。
- 具体的にグラフを彩色する方法が説明されているわけではない。
- 次数５の頂点と隣接頂点の関係が重要で、かつ５という小さな数であることに強く依存している。
これらの事と自分の発見した証明方法を比較すると、最大の特徴は次数が５を超えていくらでも大きくてよいように拡張できたことだとわかります。ほかの事は、平面といった条件が取り除かれますがだいたい同じです。
なぜブール代数を使うとそのような事が可能になるのか？といえば、ブール代数は論理の代数化という意味があり、“すべての”場合とか組合せを考えると、消えることがあるからです。
ある頂点で、その隣接点との辺を縮約するすべての組合せを考えると消えてくれるからです。
この場合の消えるというのは、矛盾式になって消えるということです。さらに、矛盾式であることを示すには、論理否定をとったものが恒真式であることを示したほうが簡単です。ド・モルガンの法則が使われることになります。
Hadwiger予想（定理ですが）「n色で彩色できなければ、(n+1)点の完全グラフに縮約できる」の、彩色性の否定が縮約可能性に結び付く理由がほぼ解明できたのではないかと思います。