解説３

Hadwiger予想のブール代数による証明 の「 5 矛盾式」について具体的に計算してみます。

集合C を５個の頂点の集合とします。C = { 1, 2 , 3, 4 ,5 }

集合D_i を集合C の空ではない部分集合とします。（ D_i ⊆ C,　i = 1, 2, …, 31 ）

D_i の表で 1 のある位置の頂点がその集合に含まれる頂点です。例えば D₅ = { 1, 3 } です。

色も数字で { 0, 1, 2, 3 } の４色とします。

辺の両端の色が同じであればその辺の真理値は 1（真）であり、両端の色が異なればその辺の真理値は 0（偽）と定義しています。

定義　集合C の頂点とその間の辺において、次ぎの２つの条件を同時に満たすことを、条件をJ_i とします。

• もし集合D_i が２個以上の頂点を含むならば、
  集合D_i の頂点同士を結ぶ辺のすべてが真である。
• もし集合D_i に含まれない集合C の頂点が存在するならば、
  集合D_i の頂点と集合D_i に含まれない集合C の頂点を結ぶ辺のすべてが偽である。

K₅(C)∧R(C) の最小項で条件J_iを満たすもの全体（の論理和）を論理式S_iとします。

S₅ を具体的に論理式で表すと次のようになります。

(¬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) ∨
(¬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) ∨
(¬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) ∨
(¬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) ∨
(¬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)

各頂点を４色で着色する方法のすべてで、S₁ … S₃₁ のとる真理値を表にしました（S_i の真理値）。真になるものと偽になるものが必ずあります。言い換えると、S₁ … S₃₁ のすべてが真になることも、すべてが偽になることもありません。

証明してみます。集合C の頂点の個数は２個以上とします（したがって D_i は３つ以上あります）。
C の頂点が１色で着色されている場合
　D_i を C とすれば、D_i は真となり、これ以外の D_i は偽となります。
C の頂点が複数の色で着色されている場合
　ある色で着色された頂点の集合を D_i とすると真になります。真になるものは使われている色の個数と同じ数になります。それら以外のもの、例えば C を D_i としたものは偽となります。∎

Home