くろょろぐ

はてダからはてブロに移行済み

サイクル頂点行列による四色定理の証明可能性

結論から言えば、「与えられた連結な3正則グラフが辺3彩色可能、すなわち、次数3の頂点のみからなる連結なグラフが辺3彩色可能ならば、そのグラフにさら次数2の頂点を丁度2個付け加えた連結なグラフもまた辺3彩色可能である」事と、四色定理は同値である。
面4彩色の可否は、3正則グラフの辺3彩色の可否と同値である事は述べた。が、辺3彩色の可否を証明する事自体、それほど簡単でない事も過去に言及した通りである。
そこで、これまでに多くの数学者がしてきたように、数学的帰納法により、証明する事を考える。
まず、対象となる3正則グラフには必ず、2辺国、3辺国、4辺国、5辺国、のいずれかが含まれている。これは、多面体定理から、全ての面の頂点数の平均が、
6-24/(n+4)
と算出され、決して6以上の値をとらない事から直ちにわかる。ここでnはグラフの頂点数である。
例えば、頂点数をn=20とすると、面の平均角数は5となる。
今、ある面数のグラフまでは彩色可能である事がわかっているものとし、これより一つ面が多いグラフについて考える。
詳細は省くが、2辺国と3辺国を含むグラフが彩色可能である事はほとんど自明なので、割愛する。
4辺国の場合、多少の調整が必要な場合もあるが、4辺国を取り除いてから彩色を施し、再び4辺国を元通りに戻しても彩色可能となる事が容易にわかる。
したがって、問題はグラフで最少の頂点を持つ面が5辺国の場合だけ考えれば良い。
なお、頂点が2彩色可能な3正則グラフ、すなわち、任意のサイクルが偶数頂点のグラフは必ず3彩色可能である事が自明であるが、この場合、サイクルの次元が一つ減るため、このあとの行列計算の際に都合が悪いが、実は最少のサイクルが5辺国の場合には、この事は考慮する必要がない事をここで示しておく。
まず、グラフに含まれる奇数頂点のサイクルが5辺国一つのみだった場合、この5辺国と隣接する偶数頂点のサイクルを隔てる辺を取り除いて一つのサイクルとする。面が一つへり、やはり奇数頂点のサイクルが残る。
もし5辺国の他に奇数頂点のサイクルがある場合、その2つが隣接している場合は、隣接している偶数頂点のサイクルと一つのサイクルとすれば良く、5辺国のまわりに隣接する奇数頂点のサイクルが3つ以上あれば、必ずひとつは奇数頂点のサイクルが残る。
要は、5辺国を取り除く際には適切に辺を一つ取り除いて隣接するサイクルと併合すれば、面が一つ少なく、奇数頂点のサイクルを少なくとも一つ含むグラフになる。
ここで、位数3の体上の多変数多項式について考えておく。
面頂点行列は、頂点数分の変数からなる連立多項式の係数行列と考える事ができる。各行は対応する列の成分を係数とする変数の一次結合である。各変数は彩色の方向を表す2つの数値、1か2をとり(決して0はとらない)、その一次結合は0とならなければならない。
これを対角化すると、対角化されあなかった部分の変数の一次結合は対角化された部分の(1個の)変数との和が0という事なので、これら対角化されていなかった列を係数とする変数の一次結合で表される多項式と、全ての変数とを、全て掛け合わせたものが恒等的に0とならないという条件を満たせば、このサイクル頂点行列に対応するグラフは辺3彩色可能となり、逆も成り立つ。
ここで、変数の値が1または2のいずれかしかとらないため、変数と対応する列の係数の符号をまるごと入れ換えても題意を失わない事がわかる(体格された列の符号の交換は、対応する行をまるごと符号を変える事に対応する事に注意)。
今、グラフから辺を1つだけ取り除いたとする。取り除いた辺の両端の頂点も取り除いてできた3正鵠グラフは、面の数が1つ少ないため、これは辺3彩色できる。
辺を取り除いてできた面を外周として、サイクル頂点行列を作る。外周部分の辺の上に、次数2の頂点を配置すると、サイクル頂点行列では対応する列に零でない成分ただ1つだけ存在する事になる。取り除いた辺の両端の頂点に対応する次数2の頂点をこの要領で追加する。
すると、対角化する際、この頂点を含む行を残して対角化する事ができ、対角化されあずに残った部分は正方行列となる。
ここはまだ証明できていない(つまり、これが四色定理の本質)が、このようにしてできた正方行列は正則行列となる。
すると、この行列の逆行列を求めて、この正方行列の部分に対応する多項式が0にならないような解を求める事ができる。
したがって、3正則グラフに次数2の頂点を2個付け加えたグラフはやはり辺3彩色可能であると言える。
ここで、辺3彩色されたグラフは、そのうち2色を交互につないで行くと必ずサイクルとなる事が2色のサイクルが組み合わさっている事が、頂点辺行列の研究でわかっている。
すると、付け加えた次数2の頂点には同一の2色の組み合わせ以外はあり得ない事が容易にわかる(付け加えられた2頂点が、サイクルの切れ目の両端にならなければならないから)。つまり、残りの1色で、取り除いた辺を彩色すれば、もとのグラフは辺3彩色される。
故に、元のグラフもまた四色で塗りわけられる。