Hadwiger予想のブール代数による証明

1　ブール代数による表現

ブール代数の用語を簡単に整理しておきます。

論理変数(logical variable)　真理値(truth value, logical value)として、真(true, 1) あるいは偽(false, 0) の2種類の値のどちらかしかとらない変数。命題(proposition)ということもあります。

論理演算子(logical operators)　ブール代数の演算子の定義です。

恒真式　各論理変数の任意の論理値で、真となる論理式を恒真式(tautology) といいます。
各論理変数の任意の論理値で、偽となる論理式を矛盾式(contradiction) といいいます。

標準形式(canonical normal form)　矛盾式ではない任意の論理式は、すべての論理変数を含む論理積の論理和の形式に展開することができます。また、恒真式ではない任意の論理式は、すべての論理変数を含む論理和の論理積の形式に展開することができます。これらを論理式の標準形式といいます。

すべての論理変数をふくむ論理積の項を最小項(minterm)といいます。
すべての論理変数をふくむ論理和の項を最大項(maxterm)といいます。

論理式を最小項の論理和の形式で展開したものを加法標準形(canonical disjunctive normal form, CDNF)といいます。
論理式を最大項の論理積の形式で展開したものを乗法標準形(canonical conjunctive normal form, CCNF)といいます。

ブール代数を有限単純グラフの頂点彩色に応用します。

定義　着色とは頂点に色を割り当てることです。

定義　彩色とは隣接する頂点が同じ色にならないように色を割り当てることです。

頂点x, y を結ぶ辺e_x,y を、真理値として 1 あるは 0 のどちらかをとる論理変数とします。e_x,y が 1 のときは x, y が同じ色で着色されていることに対応し、0 のときは x, y が異なる色で着色されていることに対応します。e_x,y と e_y,x は同じものとします。

グラフの頂点を整数で表し、m+1個とします。全体の集合を V とします。 V = {0, 1, 2, 3, 4, …, m} です。

集合V から、どの2つも異なる3頂点 i, j, k を選んで、次の論理式 r(i, j, k) をつくります。これは、i と j が同じ色で、j と k が同じ色なら、i と k が同じ色である、というような推移的な関係を表しています。

r(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 のすべての3頂点の組合せで r をつくり、それらすべての論理積をつくります。それを論理式R とします。また、集合V の点からつくられことを明示するため、R(V) のように表記することもあります。

集合V から、どの2つも異なるn個の頂点 を選んで、n点の完全グラフをつくり、その辺すべての論理和を k_n とします。これは、n個の頂点を n-1色以内で着色すると同じ色の2点が必ず存在する、ということを表現しています。たとえば、n = 5 とし5個の頂点を {1, 2, 3, 4, 5} とすると、k₅ は次のようになります。

k₅ ⇔
　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 のすべてのn頂点の組合せで k_n をつくり、それらすべての論理積をつくます。それを論理式K_n とします。集合V の頂点からつくられことを明示するため、K_n(V) のように表記することもあります。

命題1　すべての頂点を着色したとき、それに対応して各辺の真理値が定まります。その着色で真となる、R を加法標準形に展開したときの最小項が１つだけあります。逆に R を加法標準形に展開したときの最小項を任意に選べば、その最小項を真にする頂点の着色があります。

命題2　すべての頂点を n-1色以内で着色したとき、それに対応して各辺の真理値が定まります。その着色で真となる、K_n∧R を加法標準形に展開したときの最小項が１つだけあります。逆に K_n∧R を加法標準形に展開したときの最小項を任意に選べば、その最小項を真にする n-1色以内の頂点の着色があります。

2　射影

論理式R を加法標準形に展開し、グラフに含まれない辺を取り除いたものを、ΣR と表記することにします。K_n と R の論理積 K_n∧R を加法標準形に展開し、グラフに含まれない辺を取り除いたものを同様に、Σ(K_n∧R) と表記することにします。Σは続く論理式からグラフに含まれない辺を取り除く演算を表し、射影と呼ぶことにします。

例を使い説明します。射影で取り除かれる辺を e₁, e₂, e₃ とします。f(e₁, e₂, e₃) の射影とは、e₁, e₂, e₃ に、1, 0 を代入して得られる論理式すべての論理和です。

Σf(e₁, e₂, e₃) ⇔
　f(1, 1, 1) ∨ f(1, 1, 0) ∨ f(1, 0, 1) ∨ f(1, 0, 0) ∨
　f(0, 1, 1) ∨ f(0, 1, 0) ∨ f(0, 0, 1) ∨ f(0, 0, 0)

これは、e₁, e₂, e₃ それぞれを、¬e₁, ¬e₂, ¬e₃ に置き換えて得られる論理式すべての論理和としても同じです。

Σf(e₁, e₂, e₃) ⇔
　f( e₁,  e₂,  e₃) ∨ f( e₁,  e₂, ¬e₃) ∨ f( e₁, ¬e₂,  e₃) ∨ f( e₁, ¬e₂, ¬e₃) ∨
　f(¬e₁,  e₂,  e₃) ∨ f(¬e₁,  e₂, ¬e₃) ∨ f(¬e₁, ¬e₂,  e₃) ∨ f(¬e₁, ¬e₂, ¬e₃)

取り除かれる辺の数がもっと多い場合、少ない場合も同様です。

射影について極端な場合を次にまとめます。f は辺の論理式とします。

• 射影で取り除かれる辺が1つもない場合は、Σf ⇔ f は恒真式。
• f が恒真式の場合は、Σf も恒真式。f が矛盾式の場合は、Σf も矛盾式。
• 射影ですべての辺が取り除かれる場合。f が矛盾式の場合は、Σf も矛盾式。f が矛盾式でない場合は、Σf は恒真式。

f を辺の論理式とすると、次の論理式は自明に恒真式です。

　f　→　Σf

対偶をとると (¬Σf) → (¬f) ですが、(¬f) → Σ(¬f) なので

　(¬Σf)　→　Σ(¬f)

は恒真式です。

eはグラフに含まれる辺（射影で取り除かれない辺）とします。次の論理式が恒真式であることが分かります。

　e∧Σf₁　⇔　Σ(e∧f₁)
　(¬e)∧Σf₁　⇔　Σ((¬e)∧f₁)

f₁, f₂ を辺の論理式とします。

f₁ → f₂ が恒真式なら Σf₁ → Σf₂ も恒真式です。

他にも公式（恒真式）として次のものが成立しています。

　Σ(f₁ ∨ f₂)　⇔　(Σf₁ ∨ Σf₂)
　Σ(f₁ ∧ f₂)　→　(Σf₁ ∧ Σf₂)

2番目の式の証明です。(f₁∧f₂) → f₁ から、Σ(f₁∧f₂) → Σf₁ です。
同様に Σ(f₁∧f₂) → Σf₂ ですから、 Σ(f₁∧f₂) → (Σf₁ ∧ Σf₂) が成立します。

グラフの辺すべての論理和を g とします。辺の添字が面倒なので、適当に番号を振って e₁, e₂, … とします。g の各項は論理否定がつかないことに注意してください。

　g　⇔　(e₁ ∨ e₂ ∨ e₃ ∨ e₄ ∨ …)

同値ですが、次のようにも書けます。

　¬g　⇔　(¬e₁ ∧ ¬e₂ ∧ ¬e₃ ∧ ¬e₄ ∧ …)

ある着色が g を偽にするなら、その着色は隣接する頂点が異なる色になっており彩色になっています。

命題3　(¬g) → ΣR は恒真式です。

命題4　グラフが n-1色では彩色不能であることと、(K_n∧R) → g が恒真式であることは同値です。

命題5　グラフが n-1色で彩色可能であることと、(¬g) → Σ(K_n∧R) が恒真式であることは同値です。

3　Hadwiger予想と同値な命題

辺の縮約とは、ある辺の両端の頂点を同一視し、かつその辺を取り除くこととします。もし多重辺が生じれば１つにまとめます。これまで述べてきたブール代数上の扱いでは、その辺の真理値を真とおくことと同じです。

辺の縮約、頂点または辺を取り除くこと（もちろん辺の両端には頂点がなくてはなりません）を繰り返して、n点の完全グラフにできること（最初からn点の完全グラフになっている場合も含みます）を、簡単に「n点の完全グラフに縮約可能」ということにします。

Hadwiger予想とは、「彩色に n色必要なグラフは、n点の完全グラフに縮約可能である」という予想です。対偶をとって「n点の完全グラフに縮約不能であるグラフは、n-1色以内で彩色できる」といっても同じです。

Hadwiger予想の n = 3 の場合は、閉路（サイクル）を含まないグラフは2色以内で彩色できるということで、自明に成立しています。そこで n ≧ 4 とします。

グラフは n-1色で彩色不能であるとします。Σ(K_n∧R) をグラフに含まれる辺の論理式として乗法標準形に展開した各項で、ΣR に含まれないものを、g, g₁, g₂, … とします。g はグラフの辺すべての（論理否定のつかない）論理和とします。定義より g, g₁, g₂, … は ΣR に吸収されません。次の論理式は恒真式です。

　Σ(K_n∧R)　⇔　g∧g₁∧g₂∧…∧ΣR

もし、g₁が存在するとすれば、g₁ の論理否定のついた辺を縮約すれば、より小さい n-1色で彩色不能なグラフになります。

つまり、いくつかの辺を縮約してより小さい n-1色で彩色不能のグラフにする方法がもしあれば、ブール代数の機械的な計算で乗法的標準形に展開することによって見つけることができます。膨大な計算となり現実的な方法ではありませんが、グラフの構造を分析することなしに（理論的には）できるのは、大きな長所です。

Hadwiger予想が正しければ、n-1色で彩色不能なグラフで、辺を1本以上縮約して n-1色で彩色不能なグラフにする方法がないグラフは、n点の完全グラフ(孤立した頂点を含んでもよい)だけです。したがって、次の命題6, 7 は、Hadwiger予想と同値です。

命題6　Σ(K_n∧R)　⇔　g∧ΣR　が恒真式であることと、グラフが n点の完全グラフ（と孤立した点がある場合もある）であることは同値です。

命題7　Σ(K_n∧R)　⇔　ΣR　が恒真式であることと、グラフが n点の完全グラフに縮約できないグラフであることは同値です。

（注意）Σ(K_n∧R) 自体が恒真式となる場合は、乗法標準形に展開できませんが、その場合はグラフが木、林、孤立頂点などからなるグラフであることが証明でき、2色以内で彩色可能となります。そのため取り扱わないことにします。

4　最小反例の性質

Hadwiger予想に対する最小反例の性質を説明します。

最小反例となるグラフは次ぎの性質をもちます。

• n点の完全グラフに縮約することができません。（辺を縮約する、辺を取り除く、頂点とそれに接続している辺を取り除く、ことを繰り返しても n点の完全グラフにすることができません。）
• n-1色以内では彩色不能ですが、1つでも辺を取り除いたり縮約した場合、1つでも頂点を取り除いた場合は、n-1色以内で彩色可能になります。

命題8　最小反例は連結なグラフ（１つにつながったグラフ）です。n+1個以上の頂点をもち、完全グラフではありません。

定義　最小反例は完全グラフではないので、他のすべての頂点に隣接しているのではない頂点があります。その頂点の１つを、頂点0 とし、頂点0 に隣接している頂点の集合を H とします。（明らかに集合H は n-1個以上の頂点を含みます）

定義　最小反例から、頂点0 と頂点0 に接続している辺を取り除いたグラフを G' とします。

定義　グラフG' に対して着色の条件X, Y を定めます。

• 条件X: すべての頂点を n-1色以内で着色します。
• 条件Y: すべての頂点を n-1色以内で着色しますが、集合H の頂点は n-2色以内で着色します。

命題9　グラフG' は、条件X の着色で、すべての辺の真理値を偽にすることができます。また、条件Y の着色で、すべての辺の真理値を偽にすることは不可能です。

命題10　条件X の着色に対応する論理式は K_n∧R であり、条件Y の着色に対応する論理式は K_n-1(H)∧K_n∧R です。

定義　K_n-1(H) を k と表記します。k∧K_n∧R は、K_n-1(H)∧K_n∧R の意味です。

定義　辺を縮約するときに、両端の頂点の少なくとも一方が集合H に属する点であるときに限り、合併されてできた頂点を集合H の頂点であるとします。この定義にしたがう縮約である場合、「集合H に向かって縮約する」などと言うことにします。

命題11　Hadwiger予想の n-1 の場合が正しいと仮定します。集合H に向かって縮約して、集合H の頂点で n-1点の完全グラフをつくることが不可能なグラフであることと、つぎの論理式が恒真式であることは同値です。

　Σ(k∧R)　⇔　ΣR

定義　グラフG' の辺すべての論理和を g とします（g の各項は論理否定がついていません）。

命題12　グラフG' では、
　Σ(k∧K_n∧R)　⇔　Σ(K_n∧R)　は恒真式ではありません。
　Σ(k∧K_n∧R)　⇔　g∧Σ(K_n∧R)　は恒真式です。

Hadwiger予想が正しければ、命題12の論理式の条件を満たすグラフは集合H の外に辺を持たないことになります。強力な条件になっていることが分かります。

（注意）Σ(k∧K_n∧R) 自体が恒真式となる場合は乗法標準形に展開できません。その場合もやはりグラフG' が木、林、孤立頂点などからなるグラフであることが証明でき、2色以内で彩色可能となります。そのため取り扱わないことにします。

定義　論理式の先頭に tautology と書いて恒真式であることを表すことにします。

命題13　グラフG' では、

　tautology　(K_n∧R)　→　{ Σ(k∧K_n∧R)　⇔　g }

定義　集合H に含まれていない頂点の1つを選び、頂点v とします。

定義　 グラフG' において、頂点v 以外の頂点の集合を A とします。頂点v と、頂点vに隣接している（辺で結ばれている）頂点の集合を B とします。（集合B は、頂点v を含んでいます。）
集合A とB の共通部分を C とします。（集合C は、グラフG' において頂点vに隣接している頂点の集合で、n-1個以上の頂点があります。）

定義　P　⇔　[K_n(A)∧R(A)],　Q　⇔　[K_n(B)∧R(B)]

命題14　射影をとる前に、頂点v の辺でグラフG' にふくまれない辺を取り除いても、射影をとった結果は同じです。すなわち、次の論理式は恒真式です。

　tautology　Σ(K_n∧R)　⇔　Σ(P∧Q)
　tautology　Σ(k∧K_n∧R)　⇔　Σ(k∧P∧Q)

5　矛盾式

集合C とはグラフG' における頂点v の隣接点の集合です。

集合C に含まれる頂点の数を #C とすると、集合C の空でない部分集合の個数は (2^(#C)) -1 個です。

imax = (2^(#C)) -1 とします。

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

まずは、集合C に２個以上の頂点があるものとします。

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

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

定義　集合C の頂点とその間の辺において、次ぎの２つの条件のうち少なくとも一方を満たすことを、条件を¬J_i とします。

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

K_n(C)∧R(C) の最小項で条件J_iを満たすもの全体を論理式S_iとし、¬J_iを満たすもの全体を論理式S_¬iとします。

　tautology　(K_n∧R)　→　[ S₁ ∨ S₂ ∨ … ∨ S_imax ]

これは明らかに成立しています。K_n(C)∧R(C) の最小項は J_i のどれかを満たします。

ド・モルガンの法則により次の論理式に変形できます。

　tautology　(K_n∧R)　→　¬[ ¬S₁ ∧ ¬S₂ ∧ … ∧ ¬S_imax ]

K_n∧R を仮定しているので、¬S_i は S_¬i と同値です。ゆえに

　tautology　(K_n∧R)　→　¬[ S_¬1 ∧ S_¬2 ∧ … ∧ S_¬imax ]

となります。

集合C に含まれる頂点が１個だけの場合は、i = 1 のみで、S₁ は真、S_¬1 は偽と定義します。（ただし、今は反例となるグラフG' を問題にしているので、集合C には n-1個以上の頂点があるものとします。）

これで K_n∧R を仮定していれば、S_¬1 ∧ S_¬2 ∧ … ∧ S_¬imax が矛盾式となることがわかりました。

定義　Q_i と Q_¬i を定義します。

　tautology　Q_i　⇔　S_i∧Q

　tautology　Q_¬i　⇔　S_¬i∧Q

この定義より次の式が成立しています。

　tautology　Q　→　{ ¬Q_i　⇔　Q_¬i }

　tautology　Q　→　{ Q_i ∨ Q_¬i }

定義　P_i と P_¬i を定義します。

　tautology　P_i　⇔　S_i∧P

　tautology　P_¬i　⇔　S_¬i∧P

この定義より、P_i は P∧Q に 頂点v と D_i の頂点を結ぶ辺すべてに真理値１を代入し、それ以外の頂点v の辺に真理値０を代入したものになります。

Q を仮定していれば、 Q_¬1 ∧ Q_¬2 ∧ … ∧ Q_¬imax と (¬Q₁) ∧ (¬Q₂) ∧ … ∧ (¬Q_imax) の両方とも矛盾式です。命題としておきます。

命題15　グラフG' において次式が成立します。

　tautology　Q　→　¬[ Q_¬1 ∧ Q_¬2 ∧ … ∧ Q_¬imax ]
　tautology　Q　→　¬[ (¬Q₁) ∧ (¬Q₂) ∧ … ∧ (¬Q_imax) ]

6　証明

以下の証明方では、Σ(k∧P_i) 自体が恒真式となるときは乗法標準形に展開することができずにうまくいきません。しかし、その場合はグラフG' から頂点v を取り除いたグラフは木などの簡単なグラフとなります。グラフG は３色以内で彩色可能となり、n が4以上の Hadwiger予想の反例とはなりません。

命題16　グラフG' において次式が成立します。

　tautology　P_i　→　Σ(k∧P_i)

命題17　グラフG' において次式が成立します。

　tautology　(K_n∧R)　→　[ Σ(k∧P_i) ∨ Q_¬i ]

命題18　グラフG' において次式が成立します。

　tautology　(K_n∧R)　→　[ { Σ(k∧P_i) ∨ Q_¬i }　⇔　{ Σ(k∧P_i∧Q_i) ∨ Q_¬i } ]

命題17より

　tautology　(K_n∧R)　→　[ Σ(k∧P_i) ∨ Q_¬i ]

が成立しています。(K_n∧R) を仮定しているので命題18より、Σ(k∧P_i) を Σ(k∧P_i∧Q_i) に置き換えても成立します。

　tautology　(K_n∧R)　→　[ Σ(k∧P_i∧Q_i) ∨ Q_¬i ]

ここで

　tautology　Σ(k∧P_i∧Q_i)　→　Σ(k∧P∧Q)

が自明に成立しています。したがって

　tautology　(K_n∧R)　→　[ Σ(k∧P∧Q) ∨ Q_¬i ]

がすべての i で成立します。

　tautology　(K_n∧R)　→　[ { Σ(k∧P∧Q) ∨ Q_¬1 }∧{ Σ(k∧P∧Q) ∨ Q_¬2 }∧ … ∧{ Σ(k∧P∧Q) ∨ Q_¬imax } ]

Σ(k∧P∧Q) を括りだします。

　tautology　(K_n∧R)　→　{ Σ(k∧P∧Q) ∨ (Q_¬1 ∧ Q_¬2 ∧ … ∧ Q_¬imax) }

命題15 より (Q_¬1 ∧ Q_¬2 ∧ … ∧ Q_¬imax) は矛盾式としてよいので

　tautology　(K_n∧R)　→　Σ(k∧P∧Q)

が成立します。すなわち

　tautology　(K_n∧R)　→　Σ(k∧K_n∧R)

が成立します。(K_n∧R) からグラフG' に含まれない辺すべてを取り除いたものが Σ(K_n∧R) ですから

　tautology　Σ(K_n∧R)　→　Σ(k∧K_n∧R)

となりますが、逆の Σ(K_n∧R) ← Σ(k∧K_n∧R) は自明な恒真式です。よって

　tautology　Σ(K_n∧R)　⇔　Σ(k∧K_n∧R)

が成立します。これは命題12に矛盾します。反例となるグラフG' は存在しません。∎

7　定理と系

以上より、Hadwiger予想より少し詳しい次の定理が成立していることが分かります。

グラフを彩色するのに n色必要で、ある頂点v と v に接続する辺を取り去っても、やはり n色必要であるとき、頂点v を可約な頂点ということにします。頂点u, v の2点が可約な頂点であるとしても、u を取り除いたグラフで v が可約とは限らない（ u, v の2点を取り除いたグラフは n-1色で彩色できることがありえる）ので、注意が必要です。

次の系も成立しています。

系１　彩色するのに n色必要なグラフで、2つの頂点 u, v が隣接しているとします。u, v を結ぶ辺 e_u,v を縮約したグラフが n点の完全グラフに縮約不能ならば、u, v 両方共に可約な頂点ではありません。

系２　彩色するのに n色必要なグラフで、ある頂点v に隣接する頂点を v₁, v₂, …, v_m とし、v とこれらの頂点を結ぶ辺を e₁, e₂, …, e_m とします。e₁ を縮約したグラフ, e₂ を縮約したグラフ, …, e_m を縮約したグラフ, のすべてが n点の完全グラフに縮約不能なグラフであるならば、v, v₁, v₂, …, v_m は可約な頂点ではなく、これら以外のすべての頂点は可約です。