四色問題を解く。

数学の一分野であるグラフ理論の四色定理と、その一般化であるHadwiger予想のブール代数による証明を発見しました。

Hadwiger予想（Hugo Hadwiger 1943）とは、簡単に説明するなら、有限単純グラフの頂点彩色に関する予想であり、彩色にn色必要なグラフは辺の縮約を繰り返してn点の完全グラフにすることができるという主張です。

平面には５点の完全グラフは交差することなしには描けないことが知られています。四色問題は平面の位相幾何学的な性質に関する“５人の王子の問題”と、純粋に論理的な性質である“Hadwiger予想 n = 5 の場合”に分解することができます。そのため、Hadwiger予想が四色定理の一般化であるというのは、間違いではないものの多少違和感があるかもしれません。

ともかく、地図の色分けから発見されたとされる四色問題は、1976年にアッペル、ハーケンらの手作業と計算機による膨大な場合分けで解決されたことになっています（この証明は美しい、美しくないの問題以前に検証するのが困難です）。しかし、Hadwiger予想に関しては部分的にしか解決されていませんでした。

四色定理にしても、なぜ４色で十分なのか？という疑問に答えることができる簡潔な証明が望まれます。

そのための手法の第一が、Hadwiger予想そのものです。グラフが描かれた空間の性質ではなく、グラフそのものの性質として論じることができ、問題が簡略化されます。

第二は、ブール代数の応用です。辺を命題あるいは論理変数とし、両端の頂点の色が等しいときは真理値１をもち、異なるときは真理値０をもつと定義することにより、グラフの頂点の着色に関する事柄を合理的に表現することができます。例えば、グラフを彩色（塗分ける）ということは、グラフの辺すべての真理値を０にすることです。辺を縮約するということは、その辺の真理値を１に固定するということです。

これは、なぜグラフの彩色と辺の縮約が関係するのか？という疑問の答えになっています。

さらに、完全グラフに縮約する方法があるならば、ブール代数の形式的な計算により見つけることが原理的には可能となります。そのため、グラフの構造の細かな分析なしに Hadwiger予想の証明ができます。

結局、Hadwiger予想（定理）とは何か？というと“ディリクレの鳩巣原理のグラフへの論理的な拡張”と言えます。グラフの頂点が鳩で、色が巣です。鳩は互いに「コイツとは絶対に同じ巣に入りたくない」と思っている関係があって、それがグラフの辺で表されます。全ての鳩が巣に収まるには、いくつの巣が必要かが問われます。必要な巣の数の上限を述べているのがHadwiger予想（定理）です。互いに嫌っているにもかかわらず、辺でつながっている２羽の鳩を１羽に合体させることを繰り返します。そうして、どの２羽も互いに嫌ってる５羽の鳩になることが無ければ、巣は４つで十分です。

なぜ、辺の両端を異なる色にすることと、同じ色にするという正反対のことが関係するのか？と考えると、０と１しかない“狭い世界”だからだと思います。あくまでもブール代数が本質的です。

任意に与えられた５点の完全グラフに縮約不可能なグラフが４色以内で彩色できることを幾何的に証明するよりも、５点の完全グラフに縮約不可能であるという条件が４色以内で彩色できるという条件を論理的に含み、より大きなグラフであっても変わらないことを証明すると考えた方が簡単です。