解説１

頂点の集合を V として、m個の頂点が含まれているものとします。V = {1, 2, 3, 4, …, m}

V の中から異なる３つの頂点を選び出し、i, j, k とします。次の３つのグラフに対応する論理式をつくります。

　( e_i,j ∨ ¬e_i,k ∨ ¬e_j,k)　∧　 (¬e_i,j ∨  e_i,k ∨ ¬e_j,k)　∧　 (¬e_i,j ∨ ¬e_i,k ∨  e_j,k)

これを、V から異なる３頂点を選ぶすべての組合せで行い、それらすべての論理積を R とします。

R は、m(m-1)(m-2)/3! * 3 個の項の論理積として定義されたことになります。

V の異なる２頂点 x, y を結ぶ辺 e_x,y に真理値 1 を代入してみます。

V から選ぶ３頂点の組を４種に分類します。

1. x と y の両方を含んでいる
2. x を含み y を含んでいない
3. x を含まず y を含んでいる
4. x と y の両方を含んでいない

1の組からつくられるのを R^xy とし、2の組からつくられるのを R^x 、3の組からつくられるのを R^y 、4の組からつくられるのを R' とします。次の恒真式が成立します。

　tautology　R　⇔　R^xy∧R^x∧R^y∧R'

R^xy の中の３頂点の組 {x, y, z} を取り出します。

　( e_x,y ∨ ¬e_x,z ∨ ¬e_y,z)　∧　 (¬e_x,y ∨  e_x,z ∨ ¬e_y,z)　∧　 (¬e_x,y ∨ ¬e_x,z ∨  e_y,z)

e_x,y に真理値 1 を代入します。

　(e_x,z ∨ ¬e_y,z) ∧ (¬e_x,z ∨ e_y,z)

　(e_x,z ∧ e_y,z) ∨ (¬e_x,z ∧ ¬e_y,z)

さらに次のように書いても同値です。

　e_x,z ⇔ e_y,z

例えば x = m-1, y = m と仮定すると、R^xy の e_x,y に真理値 1 を代入したものは次のようになります。

　(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)

ゆえに e_x,y∧R を次のように表すことができます。

　e_x,y∧(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)∧R^x∧R^y∧R'

R^x か R^y のどちらか片方はなくても同値になることがわかります。

　e_x,y∧(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)∧R^x∧R'

e_x,y の真理値が 1 である場合は、e_x,z と e_y,z は同じ真理値をとるようになり、したがって同じ辺とみなしてよいことがわかります。

すなわち e_x,y を 1 にすることと、辺e_x,y を縮約することが同じ効果になります。これは R^xy の作用によるものです。

５頂点の完全グラフを論理式にします。

　( e_1,2 ∨ e_1,3 ∨ e_2,3 ∨ e_1,4 ∨ e_2,4 ∨ e_3,4 ∨ e_1,5 ∨ e_2,5 ∨ e_3,5 ∨ e_4,5 )

これを、V から異なる５頂点を選ぶすべての組合せで行い、それらすべての論理積を K とします。

K は、m(m-1)(m-2)(m-3)(m-4)/5! 個の項の論理積として定義されたことになります。

V の異なる２頂点 x, y を結ぶ辺 e_x,y に真理値 1 を代入してみます。

V から選ぶ５頂点の組を４種に分類します。

1. x と y の両方を含んでいる
2. x を含み y を含んでいない
3. x を含まず y を含んでいる
4. x と y の両方を含んでいない

1の組からつくられるのを K^xy とし、2の組からつくられるのを K^x 、3の組からつくられるのを K^y 、4の組からつくられるのを K' とします。次の恒真式が成立します。

　tautology　K　⇔　K^xy∧K^x∧K^y∧K'

　tautology　K∧R　⇔　(K^xy∧K^x∧K^y∧K')∧(R^xy∧R^x∧R^y∧R')

x = m-1, y = m と仮定すると、e_x,y∧K∧R は次のようになります（K^xy は e_x,y に吸収されます）。

　e_x,y∧(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)∧(K^x∧K^y∧K')∧(R^x∧R^y∧R')

K^y と R^y を取り除いても同値になることがわかります。

　e_x,y∧(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)∧(K^x∧K')∧(R^x∧R')

e_x,y の真理値が 1 である場合は、e_x,z と e_y,z は同じ真理値をとるようになり、同じ辺とみなしてよいことがわかります。

e_x,y を 1 にすることと、辺e_x,y を縮約することが同じ効果になります。

(K^x∧K')∧(R^x∧R') は、V から y を取り除いた集合 V-y から、K, R を構成し、掛け合わせたものになります。これは辺を縮約する方が、彩色するより再帰的で都合の良い性質を持つことを意味します。

Hadwiger予想には、四色問題の「なぜ四色で十分なのか？」という疑問に対する洞察が含まれており、その分問題を簡単にしています。Hadwiger予想は四色問題の一般化であると同時に簡略化でもあります。

平面グラフのような５点の完全グラフに縮約できないグラフG を用意します。G のすべての頂点に４色から色を割り当て、G の各辺のとる値を調べます。辺の値は次のように定義します。

• x と y が同じ色の場合は e_x,y は 1 です。
• x と y が違う色の場合は e_x,y は 0 です。

４色を割り当てるすべての方法で、各辺の値を調べて表にすることが出来ます。同様に５色から各頂点に色を割り当てるすべての方法からの表もつくり、両者を比較します。

表といっても、正確には G の各辺の真理値 0 または 1 が決められた順序で並んだベクトル（タプルのほうがいいかもしれません）の集合と思ってください。

グラフG は４色では彩色不可能なグラフでかつ頂点の個数が最小のもの、Hadwiger予想の n = 5 の場合（あるいは四色定理）に対する最小反例であったとします。

• ４色からの表には、G のすべての辺を 0 にするものはありません。（４色では彩色不可能と仮定されているからです）
• ５色からの表には、G のすべての辺を 0 にするものがあります。（最小性からの帰結です）

G の辺を任意に１つ選び e_x,y とします。表から e_x,y = 1 になっている部分を抜き出し比較します。これは頂点 x と y が同じ色に限定されるので、実質 x と y は同じ頂点とすることと同じで、e_x,y を縮約することと同じ意味を持ちます。e_x,y を縮約してしまえば頂点の個数が少なくなるので４色でも５色でも彩色可能です。

• ４色からの表の e_x,y = 1 になっている部分には、G の e_x,y 以外のすべての辺が 0 になっているものがあります。
• ５色からの表の e_x,y = 1 になっている部分には、G の e_x,y 以外のすべての辺が 0 になっているものがあります。

この方法を繰り返していけば、G のすべての辺が 0 になっているもの以外は、４色からの表と５色からの表とでは違いがないことがわかります。

ただし、複数の辺を縮約したときはループ（辺の両端の頂点が同じ頂点である辺）になる場合があります。その場合はその辺も 1 と仮定します。あるいは、５色からの表からすべての辺が 0 ではないものを１つ取り出し、そこで 1 になっている辺すべてを縮約することで４色からの表にも含まれていることを確認するという方法もあります。

こうして、最小反例は簡単で顕著な性質を持つことが分かります。縮約してできるグラフすべてをまとめて扱うことで、最小反例の性質の特異性が際立っています。

グラフG は連結かつ完全グラフではなく、４色で彩色不可能だけど５色では彩色可能だと仮定し、Hadwiger予想の n = 5 の場合が成立していると仮定してみます。

• ４色からの表には、G のすべての辺を 0 にするものはありません。（４色では彩色不可能と仮定されているからです）
• ５色からの表には、G のすべての辺を 0 にするものがあります。（５色で彩色可能と仮定されているからです）

他にも５色からの表に含まれていて４色からの表には含まれていないものがあるはずです。Hadwiger予想が成立するなら、グラフG は５点の完全グラフに縮約可能なはずです。５点の完全グラフに縮約するのに縮約する必要のある辺が 1 で他の辺は 0 になっているものは、５色からの表に含まれていて４色からの表には含まれていません。５点の完全グラフは５色で彩色可能ですが４色では彩色不可能だからです。

もっと他に５色からの表に含まれていて４色からの表には含まれていないものがあれば、1 になっている辺を縮約することにより、５色で彩色可能で４色で彩色不可能なグラフになります。

Hadwiger予想の n = 5 の場合が成立しているとすると、４色からの表と５色からの表に違いがなければ、５点の完全グラフに縮約することは不可能と判断できることになります。

逆にHadwiger予想の n = 5 の場合を証明するには、グラフが５点の完全グラフである場合を除いて、両者の違いがグラフのすべての辺を 0 にするもののみという状況が決して生じないことを明らかにすればよいことになります。ブール代数を使うのが最も自然な方法と思われます。

「なぜ四色で十分なのか？」などと書いてますが、多くの人が気がつくように「５点の完全グラフが交差することなしには平面に描けないから」です。本当に求められているのは、「５点の完全グラフが平面には描けないから４色以内で彩色できる」ということを数学的に正しく表現することです。

ブール代数を使う表現では辺の論理和がよく使われます。

　e_1,2 ∨ e_1,3 ∨ e_1,4 ∨ …

集合の演算で表現すると次のようになります。

　{e_1,2} ∪ {e_1,3} ∪ {e_1,4} ∪ …

辺の論理積もよく使います。

　e_1,2 ∧ e_1,3

これを上記のように形式的に集合演算に対応させると、空集合∅になってしまいます。

　{e_1,2} ∩ {e_1,3} = ∅

つまり、ブール代数を使う方法というのは、単純に辺の集合などを扱う方法と比較してみると、空集合を分析する方法になっています。

頂点すべての色を指定するベクトルを定義しておき、辺を真にする色のベクトルの集合へ対応させる写像をφとします。すると

　φ(e_1,2) ∩ φ(e_1,3)

も集合の演算として意味を持ち、ブール代数による表現を避けることができます。ただしブール代数を使った方が簡潔で見通しがよくなります。グラフを彩色するというのは辺の両端の頂点に異なる色を割り当てることですから、辺から色への写像を考察するのは当然のことです。したがってブール代数を使うのも極めて自然なことです。

それで、写像という概念について調べてみると ガロア理論の推移史について 中村幸四郎 というのがありました。「集合」+「写像」という概念を基礎に理論を展開するという方法はデデキント（Richard Dedekind 1831‐1916）が始めたようです。ガロア論文を整理して整数論に応用するという目的があったようです。それに「一次従属・独立の理論」「ベクトル空間」がこの デデキント体論 から始まったというのも驚かされます。

「写像」という概念には天才ガロア（Évariste Galois 1811‐1832）の大きな影響があるということでしょう。ただ、類似の概念として「関数」があります。関数を工夫して問題を解くということはあります。写像を工夫してある集合の性質を分析するというのは、当たり前の方法です。ブール代数が使われることに抵抗を感じる必要はまったくありません。

Home