四色問題を解く。

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

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

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

ともかく、地図の色分けから発見されたとされる四色問題は、1976年にアッペル、ハーケンらの手作業と計算機による膨大な場合分けで解決されたことになっています。そのためコンピューターを必要とする方法でしか証明できないと誤解されている方が多いようです。

辺の縮約というのは自然に頂点の個数に関する帰納的性質を持つため、Hadwiger予想をブール代数で表現するのは簡単です。

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

代数的な手法により深い分析ができるようになり、任意次数の頂点の可約性が証明できます。

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