地図の四色彩色問題が、境界線の三色彩色問題（すなわち、グラフの辺彩色）である事を示し、特に３正則グラフが辺３彩色可能となる条件について考察する。
これは論文の覚書みたいなもの。文体や図表、数式などはあとからちょくちょく加除添削する事になると思う。困った事に当方はグラフ理論は全くの素人で、用語法などを間違えている可能性があるので、悪しからず。
〔最終更新：2022-11-26〕
地図を四色に塗分けると、その境界線は三色に塗分けられる
ここでは、何故、四色問題を考える上で、地図の境界線がかかわってくるのか考える。
四色問題を考えるなら、三色で塗分けられる地図も四色使って塗分けるべき
四色問題を考えるにあたって、地図の彩色数を求める必要はない：常に四色を使ってみて、塗り分けられるか塗分けられないかだけを気にすれば良い。
その方針に則って、普通よくするように、平面グラフの頂点を四色で彩色する事から考え始めた。
頂点の彩色とは、どの辺の両端も同色にならないように頂点に着色する事である。この彩色に必要な最低限の色数の事を彩色数と呼ぶ。
グラフの種類はできるだけ少なく、条件はできるだけ厳しく
問題を解くにあたって、対象となるグラフの種類はできるだけ少なく、単純な方が良い。
例えば、四色問題に直接関わらない辺や頂点、すなわち次数が２以下の頂点は、あとからそれらの辺や頂点を付け加えても彩色数が四以下になる事が自明なため、取り除く事ができる。同様の理由で、次数３の頂点のうち、完全グラフの一部となっている頂点も取り除く事ができる。
さらに、逆にグラフに辺を付け加えて全ての面が三角形になるようにし、このグラフが四色で彩色できる事を示せば、このグラフから辺を取り除いてできる全てのグラフで四色で彩色できる事が同時に示される事になる。
与えられたグラフの面を全て三角形化する方法には大きく二つの方法がある。
- 一つは、全ての面に対角線を追加する事。
- もう一つは、（四角形以上の）全ての面の中に頂点を追加し、そこからその面の全ての頂点に辺をつなぐ事。
前者は頂点数に変化がないが対角線の配置にいくつものバリエーションがある。頂点数が変化しないため、頂点数による数学的帰納法を使える余地が考えられる。
一方、後者は頂点数が増す代わりに辺の配置方法が常に一通りとなる。頂点数が変わる事で数学的帰納法が使いづらいかもしれないが、面を構成する全ての頂点が同一の頂点と接続される事で、一つの面上で彩色に必要な色が三色に限定されるため、考えるべき問題が簡素化される事が期待される。
もっとも結論から言えば、どちらの方法を使ったとしても実際上の影響は無い。
グラフの彩色を方程式で表現する
グラフの彩色は、どの頂点にどんな色を着けるかを求める事であるから、これは方程式に相当する。
はじめに宣言したように、使う色は四色と決めているので、方程式は位数４の体上の多変数多項式となる。
具体的には、色を数値に対応付け、辺で繋がれた二頂点x,yについて、(x-y)が0にならなければ、xとyは異なる色であると表現できる。これを全ての辺について掛け合わせたものは、どこかで両端が同一色になる辺があるときに限り0となる多変数多項式が得られる。
余談だが、このやり方は三色問題にも応用できる：体として、位数４の体の代わりに位数３の体を使えば良い。
実は「0でない」ではなく「1である」だった
グラフを四色で彩色する方程式を実際に研究するわけだが、方程式と言っても実際は等式ではなく不等式の形をしている：四色で塗分けらる時に0以外の値をとるからだ。なので、実際問題として四色で塗分けられる時に、式がどんな値をとるか考えてみる事にする。
まず、全ての面が三角形となっているため、三角形x,y,zからなる多変数多項式(y-z)(z-x)(x-y)について考えてみる。
が、実際に計算してみると、面白い事に、x,y,zが互いに異なるどんな値をとった場合でも、(y-z)(z-x)(x-y)の値は常に1となる事がわかる。
グラフ全体で考えると、各面の三角形の式を全て掛け合わせたものが、グラフの式を二乗したものになる。このグラフが四色で塗分けられる時、全ての面に於いて、面の式が1なのであるから、グラフの式を二乗したものも1になる。元のグラフの式は、この式を開平した物であるから、グラフの式は1か(-1)のどちらかの値をとる事になる。
ここで、位数４の体、すなわち位数４のガロア体のどの元も、自分自身が自分自身の（和の）逆元である、つまり1と(-1)には区別がなくどちらも1であるため、元のグラフが四色で塗分けられると、式の値はちょうど1となると言える。
三角形の頂点が四色で塗分けられる時は、三角形の辺が三色で塗分けられている
実は、三角形x,y,zが互いに異なる値の時、これら三つの変数の差(y-z),(z-x),(x-y)も全て（0以外の）異なる値になる。いわば、一つの面について、各辺が異なる色に彩色されたと言える。これは、四色問題を三色問題の特別な場合として考える事ができる事を表している。
四色問題の方程式は三次方程式であるが、三色問題の方程式は二次方程式となるため、方程式を解くのがいくらか簡素化されるはずである。
そこで、各三角形の頂点を面に、辺を頂点に置き換えた新たなグラフを考える：この新しいグラフには、全ての頂点の次数が４、すなわち４正則グラフであるという特徴がある。全ての頂点の次数が偶数であるから、この事は四色問題と一筆書き（オイラーサイクル）の間に何らかの関係がある事を示唆しているかのようである（尤も、実際にはこの形のグラフに於いては明確な関連は無かったのだが）。
４正則グラフから３正則グラフへ
新たな４正則グラフは三角形が網のように連なっているという特徴がある。そして、この個々の三角形の頂点がちょうど三色で塗分けられる事になるため、その三頂点は全て異なる色となり、三角形毎にどの順序で頂点を彩色するか、つまり右回りか左回りか、が決まればグラフの彩色が完成する事になる。
そこで、また新たに、このグラフの面（三角形）を頂点に、頂点を辺に、置き換えたグラフを考えると、全ての頂点の次数が３、すなわち３正則グラフが得られる。そして（４正則グラフの）頂点の三色問題は、辺の３彩色問題に置き換えられる。
全ての地図の境界線は３正則グラフに対応する
ここで最初のグラフに振り返ってみる。
元のグラフの頂点は、その元になった地図の領域（面）を頂点に、接する二領域の境界線はそれを横切る辺へ、と置き換えられたものである。
その次に得られた４正則グラフは、頂点を面へ、辺を頂点へ、置き換えたもの。
最後に得られた３正則グラフは、頂点を辺へ、面（三角形）を頂点に置き換えたものである。
もし仮に地図の境界線が元から３正則グラフであったならば、つぎのように整理される：
- 地図の領域（面）→頂点→面→面
- 地図の境界（辺）→辺→頂点→辺
- 地図の境界の頂点→面→面→頂点
つまり、最終的に得られた３正則グラフは、めぐりめぐって元の地図の境界線の（３正則）グラフに戻るのである。
この遠回りで無駄に見える手順により、地図の境界線に、ガロア体上の多変数多項式という意味付けがなされたわけである。
ところで、普通の地図の境界線の頂点には次数が３でないものもあるはずである。これを解決する方法はシンプルである：
- 次数が３を超える頂点の上に、新たに領域を配置する。この領域はあとで削除しても、彩色に影響しない事は容易に理解できる。これは、はじめのグラフの面を三角形化する際に、面の中に新たに頂点を一つ追加する事に対応する。
- または、辺を互い違いにずらして国境線を増やす。あとで国境線を縮めて元の位置に戻しても、やはり彩色に影響はない。これは、はじめのグラフの各面に対角線を追加する事に対応する。
結論
グラフの頂点の彩色と同様に、グラフの辺の彩色というのがある：すなわち、どの頂点についても、その頂点に接続するどの辺も同一色にならないように辺の着色をする事を、辺の彩色という。
そしてここまでの議論により、地図の領域の四色問題は、地図の境界線（に対応する３正則グラフ）の辺の３彩色問題に帰着するわけである。
３正則グラフの辺を三色で塗分けるには
ここでは、辺が３彩色された３正則グラフの性質を調べ、辺が３彩色可能となる条件について考察する。
なお特に断りない限り、ここでは３正則グラフは連結でループを持たないものとする（多重辺は構わない）。
特定の二色に着目すると、サイクルになる
３正則グラフの辺彩色を考える上で、サイクルは非常に大きな役割を担っている。
特に、３正則グラフは、頂点の数は常に偶数であり、辺の数は３の倍数（頂点数の二分の三）となるから、全ての頂点を含むサイクル（ハミルトンサイクル）は、二色で辺を交互に塗分ける事ができる。そうすれば残った辺を残りの一色で塗れば、辺の３彩色が完成する。
しかし残念なことに、３正則グラフがハミルトンサイクルを持つ条件については未解決問題で、実際、ハミルトンサイクルを持たない３正則グラフが存在する。
そこで、３正則グラフの辺がもう既に三色で彩色されていると仮定する。
そして特定の二色だけに着目し、適当な頂点から出発して、色が交互になるように辺を追いかける。すると、全ての頂点の次数が３である事から、必ず偶数個の頂点を通って、出発点の頂点に戻ってくるサイクルとなる。全ての頂点を通るとは限らないから、残った頂点について同じ事を、また同じ二色について行うと、同じように偶数個の頂点を通って、サイクルとなる。これを頂点が残らなくなるまで繰り返す。ちなみに、多重辺の場合はちょうど２個の頂点を行って戻ってくるだけだが、これもれっきとしたサイクルである。
このように、互いに交わらず、グラフの全ての頂点を含む、偶数頂点のサイクルの集合が必ず得られる。逆に言えば、３正則グラフが、このようなサイクルの集合を持てば、辺を３彩色できる事になる。
頂点辺行列
次にこのようなサイクルの組を、どのようにすれば発見する事ができるか考える。
サイクルとは、別の言い方をすれば、２正則グラフであるようなサブグラフの事であるから、全ての頂点に於いて２正則であるようなサブグラフを求める方程式を考えれば良い。
頂点は全て使うのだから、辺の有無を未知数とした連立方程式と言う事になる。そこで、頂点を行、辺を列とした、頂点辺行列を導入する。
グラフの各頂点と各辺について、頂点xが辺yに接続している時、対応する行x列yの要素が1、それ以外が0となる行列を考える。そして未知数ベクトル（サブグラフに対応）は、そのそれぞれの成分に対応する辺が、存在する時1、それ以外は0をとるものとする。すると、行列と未知数ベクトルの積は、求めるサブグラフの各頂点の次数を表す事になる。
今求めたいサブグラフは２正則グラフであるから、行列と未知数ベクトルの積の全ての成分が2になれば良い。
ところで、この行列と未知数ベクトルを実数上で定義すると、当然の事ながら解ベクトルの成分は1か0のみとはならず、有理数の解を含む事になり、このままではあまり役に立たない。
そこで実数上ではなく、どうにか工夫して、有限体上で定義したい。最終的に（ここに至った経緯は省くが）、位数２の体上で定義する事でこの問題は解決できる。この場合、サブグラフの各頂点の次数が偶数かどうかだけが問題となるため、頂点の次数が0となる解が現れ、全ての頂点をカバーするサイクルの集合のみを得る事は諦めなければならない。その代わり、解が必ず何らかのサイクルの組となっている事は担保される。
１正則グラフ
ここで気を付けたい事がある。それは、２正則グラフは必ずしも偶数頂点のサイクルになるとは限らないという事である。そこで、上で求めた２正則サブグラフから、偶数頂点のサイクルのみを持つサブグラフを絞り込む必要がある。
ここではじめに振り返ってみると、偶数頂点のサイクルに着目したのは、三色で彩色された辺のうち、二色に着目したからである。この二色はサイクル上に交互に現れるから頂点数が偶数となる。したがってそのうちのさらに一色だけに着目すれば、サイクル上のすべての頂点を通り、一つ置きに辺が現れる事になる。
これは全ての頂点で次数が１、すなわち１正則グラフである事を示している。
そこで、頂点辺行列と未知数ベクトルとの積の全ての成分が1となるように方程式を立てれば、解に１正則サブグラフが全て含まれ、その中には偶数頂点のサイクルの一部となっているものも含まれているはずである。
あとは、求めた２正則グラフの中に１正則グラフが含まれるているものだけを抽出する条件を方程式に付け加えれば良い（ここで、体が位数２のため、実際に求められる解の中には次数３のものも全て含まれる事にも注意する必要があるが、実際には頂点の次数と辺の組合せの関係で、次数が0のものと次数が3のものは、この追加の条件によって自動的に排除される）。
なお、この追加の条件は、式が行列計算の中に納まらないため、若干不格好な上に統一感がなく扱いづらく、実際には使わない。
全ての頂点を通るサイクルを求める別の方法
位数２の体上で定義された頂点辺行列についてもう少し考えてみる。
これと未知数ベクトルの積の全ての成分が2になるとは、位数２の体上では、全ての成分が0になると書き換えられる：つまり、積が零ベクトルになるという事である。
この事から、この方程式の解である、全てのサイクルの組（ベクトル）の全体は、成分同士の和によって群をなす。別の言い方をすれば、位数２の体上の有限次元ベクトル空間の部分空間となっている。サイクルの組とサイクルの組の和は、別のサイクルの組になっているという事である。
ここで、再び振り返って、３正則グラフの３彩色された辺について、三色のうち二色だけに着目する事を考える。三色の中から二色を選ぶ選び方には３通りあるが、そのうちのどの２通りを選択しても、当然だが共通の色が必ず一色存在する事がわかる。
上で見たように、一色だけに着目すると１正則グラフになり、二色に着目すると２正則グラフになるのだから、二つの異なるサイクルの組で共通部分（すなわちベクトルの成分毎の積が1になるもの）が１正則グラフになるものという条件を付けくわえても、すべての頂点をカバーしつつ、偶数頂点のサイクルの組のみを抽出できるはずである。
この方法の利点は、追加の条件を自然に同一の連立方程式の中に埋め込む事ができる点である。またこの方程式の解全体は、自動的にすべての可能な３彩色の集合となる。
結論
ここまで見てきたように、３正則グラフの辺彩色を考える上で、位数２の体上で頂点辺行列を定義する事が、非常に有効である事を示唆している。
さらに、３正則グラフのサイクルの組がベクトル空間をなす事は大きな発見であり、３彩色の条件を求める上で重要な役割を果たす。これは体の位数を２にするという工夫がなければ気付けなかっただろう。
３正則グラフが辺３彩色可能となる条件
ここでは３正則グラフの辺３彩色を可能にする条件について考察する。またそのために３正則グラフが辺彩色によってどのように分類されるかについても考える。
なお、この過程で３正則グラフの辺彩色数の最大値が４である事も見えてくるが、ここでは取り上げない。
頂点辺行列と辺３彩色との関係
３正則グラフの頂点辺行列は、その定義の仕方から、1となる要素が、各行にちょうど三つずつ、各列にちょうど二つずつ、存在する行列である。
仮にこのグラフが辺３彩色されている時、頂点辺行列の対応する各列も同色に着色されていると考え、列を入れ替えて、各色毎に全く同じサイズの三つの部分行列に分ける事ができる。
この部分行列は1となる要素が各行にちょうど一つずつの存在する行列である（言うまでもなく各列にはちょうど二つずつ）から、うまく行を入れ替えれば、単位正方行列を縦に二つ並べたような形にする事ができる。
すなわち、辺３彩色可能な３正則グラフの頂点辺行列は、少なくとも頂点数の丁度半分の階数を持つ事を意味している。
この部分行列は１正則サブグラフを表現しているわけであるから、この頂点辺行列と未知数ベクトルとの積からなる連立方程式が意味のある解を持つためには、１正則サブグラフの存在が条件の一つとなる。
３正則グラフは三種類ある
既に論じたように、３正則グラフが辺３彩色されると、着目する辺の色の数に応じて、全ての頂点をカバーするサイクルの集合（すなわち、全ての頂点を含む２正則サブグラフ）の存在と、（その補グラフである）全ての頂点を含む１正則サブグラフの存在が自明となる。別の言い方をすれば、これらのサブグラフが存在しない３正則グラフでは辺３彩色できないと言える。
しかし、１正則サブグラフが存在しさえすれば、元の３正則グラフは辺３彩色可能となるかと言えば、これには反例が存在し、成り立たない事がわかる。この事は、後述の辺の縮約による４正則グラフから詳しく知る事ができる。
以上から、3正則グラフは次の三種類に分類する事ができる：
- １正則サブグラフが存在し、辺３彩色可能な３正則グラフ。
- １正則サブグラフが存在するが、辺３彩色不可能な３正則グラフ。
- １正則サブグラフが存在しない３正則グラフ。
４正則グラフとオイラーサイクルの２彩色
３正則サブグラフが１正則サブグラフを持つ時、この１正則サブグラフの辺を縮約する事で、４正則グラフを得る事ができる（この４正則グラフはループを含んでも良い）。もし元のグラフが辺３彩色されていれば、得られた４正則グラフの各辺が残った二色で着色されている事が容易に理解できる。この時どの頂点にも同色の辺が２本ずつあるため、この二色で交互に彩色されたオイラーサイクルをうまく選択する事ができる（証明は省く）。
逆に任意の４正則グラフが与えられれば、その各頂点を適当な方向に引きはがしてその間に辺を配置すれば、（追加された辺が１正則サブグラフとなるため）必ず１正則サブグラフが存在する３正則グラフが得られる。この時あらかじめ２彩色されたオイラーサイクルをとり、頂点の引きはがしで新たに配置される辺を三番目の色に着色すれば、得られる３正則グラフの辺にはなんらかの着色がされている事になる。この際、頂点の引きはがし方（三通りある）によっては、辺３彩色されない場合がある。詳しい説明は省くが、それはその新たに配置される辺がカットエッジとなる場合、言いかえれば、その辺が、どのサイクルの一部にもなってない場合、に限られる。
余談だが、カットエッジが存在すると、その辺がつながる頂点で彩色するためには第四の色が必要になるため、任意の３正則グラフは辺４彩色可能である事が示唆される。〔追記：調べたら、ヴァイシングの定理 Vizing's Theorem というのがあって、グラフの最大次数＋１色、今回は３正則なので４色、あれば彩色できるそうです。〕
以上を整理すると：
- ４正則グラフ全体は、１正則サブグラフを持つ３正則グラフの全体と、本質的に等価である。
- 辺３彩色可能な３正則グラフの全体は、４正則グラフ全体の中に、本質的に全て含まれる。
- ３正則グラフにカットエッジが存在すれば、辺３彩色できない。
〔追記：註：なんかこの段階ですでに証明できてるっぽいです。詳細は追って追記します。〕
〔追記：註：と思ったけどやっぱり証明されてませんでした。カットエッジが存在しなくても辺３彩色できないグラフが存在しない事を言わなきゃならない。〕
〔追記〕なお、ここで４正則グラフに必ずオイラーサイクルが存在する事から、それを適当に引き剥がして作った３正則グラフには、全ての頂点を含む２正則サブグラフが必ず存在すると言える。
３正則グラフが辺３彩色できるための条件の整理
ここまでの議論では、辺３彩色の条件として１正則サブグラフが存在する事とあるが、辺３彩色されている場合、１正則サブグラフは各色毎に存在するのだから、グラフのどの辺も、その補グラフであるどれかの２正則サブグラフ、すなわちどれかのサイクルに含まれる事になる。これは、辺３彩色されている３正則グラフにはカットエッジが存在しない事と同値である。したがって １正則サブグラフが存在するという条件は不要で、３正則グラフが辺３彩色するためには、少なくともカットエッジが存在しない事、と条件を整理できる。
ここで、３正則グラフを辺３彩色するもともとの動機である、地図の四色問題に振り返ってみると、地図の境界線は必ずなんらかの領域を囲んでいるのだから、境界線のどの辺も何らかのサイクルの一部でなければならない。すなわち、地図の境界線はカットエッジを決して含まない。
したがって、カットエッジを持たない３正則グラフは必ず辺３彩色できるのではないか、という予想が立つ。
以上をまとめると、次のような予想にまとめる事ができる：
- ループを持たない３正則グラフが辺３彩色可能であるための必要十分条件は、グラフがカットエッジを持たない事である。
十分条件はすでに示されているので、以降は必要条件を証明する方法を探っていく。
頂点辺行列とカットエッジの関係
カットエッジはサイクルの一部ではないから、もし存在すれば、いかなる２正則サブグラフにも含まれず、したがってその補グラフである１正則サブグラフに必然的に含まれる事になる。
カットエッジの場所は存在すれば常に固定であるから、これは２正則サブグラフに対応する部分ベクトル空間に、決して1とならない成分、つまり常に0となる成分が存在する事に対応する。
空間全体を通して常に0になる成分が存在するならば、どのような相異なるベクトルの組にも、必ず共通して0になっているような成分が存在する事になる。
前に論じたように、３正則グラフの辺３彩色の可否と彩色は、頂点辺行列と未知数ベクトルによる連立方程式によって完全に求める事ができる：今、頂点辺ベクトルをM、二つの未知数ベクトルをx,y、その成分同士の積のベクトルをxy、成分がすべて1となるベクトルを1、零ベクトルを0、とすると、連立方程式は次のように書ける：
M[x y xy] = [0 0 1]
もしこの方程式が解を持たない時、詳細は省くが、どのようなx,yを選んでも、ともに0になる成分が存在する事が導かれる。
ここから、次のような補題の証明が必要な事がわかる：
- ３正則グラフのサイクルの組全体がなす部分空間に於いて、相異なるどのようなベクトルをとってもともに0であるような成分が必ず存在するとき、この部分空間全体を通じて共通して0であるような成分が存在する。
この補題が真ならば、カットエッジが存在しない３正則グラフの辺は３彩色可能である事が証明される。
補題の証明と四色定理
ここでいよいよ補題を証明し、四色定理がここまで議論した３正則グラフの辺３彩色性から導かれる系に過ぎない事を論じる。
…ありていに言えば、コンピューターを使用しなくとも、四色定理が証明できる事を示す。
〔追記：註：この記事では、現段階で証明に失敗しています。〕
何を証明するか
解くべき命題は、「相異なるベクトルにいつも共通して0であるような成分が存在するなら、部分空間全体を通じて共通して0になるような成分が存在する」事である。
全空間に於いてはこの命題が成立する事が、線形代数の理論によってわかっている。しかし、部分空間に於いては反例が存在するため、一般には成立しない。
今回の場合は、頂点辺行列による条件が付された、限定された部分空間であるため、その頂点辺行列の性質を利用しなければならない。
証明しやすさのため、実際に証明するのは、対偶である：
- ３正則グラフのサイクルの組全体がなす部分空間に於いて、この部分空間全体を通じて共通して0であるような成分が存在しないならば、ともに0であるような成分が全く存在しないベクトルの組が必ず存在する。
反例の可能性がある部分群
〔追記：註：この部分群が必ず含まれると思ったが、必ずしも含まれるとは言えなかった…。なんか切れ味悪いなぁ…。orz〕
反例の可能性がある最小の部分群は、成分が７つあり、位数が８のものである（∵３つある基底の値の組み合わせがちょうど７つであるから）。
以下はその一例である。
０００００００
１１１１０００
１１００１１０
１０１０１０１
１００１０１１
０１１００１１
０１０１１０１
００１１１１０
これより成分の多いものも存在するが、必ずこの部分群を本質的に含む（∵群論により、位数が２の冪である事、元の群の位数に約数があれば、その約数を位数とする部分群が必ず存在する事、位数８の部分群は全てこの形になる事、から）
ゆえに、全ての頂点をカバーする２正則サブグラフが、この群を成さない事を示せば、すくなくともこの形の反例が存在しない事を示す事ができる。
全ての頂点をカバーする２正則サブグラフの辺の数は、調度頂点数と等しくなる事から、上に挙げた部分群の各成分を、１になる成分の合計が頂点数と等しくなるように辺に配分すればよい。これは上に挙げた部分群から零ベクトルを除いた係数行列とする連立方程式を解く事で求められる。
Vを正整数とするとき、頂点数を2Vと置いて連立方程式を解いてみると、全ての成分が同数で(V/2)個ずつ各辺に配分されなければならないという結果になる。一方、辺の数は3V本であるので、配分される全ての成分の合計もこれと一致しなければならないが、実際には(7V/2)個となって、矛盾する。したがって、このような反例は存在しない事が示される。
この部分群は反例の可能性がある全ての部分群に本質的に含まれるのであるから、位数８以上で、カットエッジが存在しない３正則グラフが３彩色されないような反例は存在しないと言える。
全ての頂点を通る時だけ決して通らない辺
全ての頂点を通るサイクルの組が位数４の部分空間を成せば３彩色できるわけだが、もし、全ての頂点を通っている時だけ決して通らない辺（全ての頂点を通っていない時は通る事もある）というものが存在すると、位数４の部分群にはならないため、３彩色できない事になる。
そこで、そのような辺が存在する条件をあらかじめ確かめておく必要がある。
もし実際そのような辺があったとすると、３正則グラフであるから、その両端に接続する辺は必ず通っている。つまり、全ての頂点を通るようなサイクルのベクトルを集めると、これらの辺に対応する５つの成分がどのベクトルも決まった値になっているという事である。一方で、全ての頂点を通らない場合にも特定のパターンになる事がわかる。
さて、その５つの成分を仮に
０１１１１
のように表したとすると、最初のビットが０の部分空間は、
０００００
０００１１
０１１００
０１１１１
のような４つのグループに分けられる。
一方、最初のビットが１であるものは、
１０１０１
１０１１０
１１００１
１１０１０
の４つのグループに分けられる。見ての通り、最初のビットが１のものは全て１となるビットがちょうど３箇所ある。
さて、全ての頂点を通る、つまり１となるビットの数が丁度頂点数と同じになるベクトルを一つとると、
０１１１１ １…((2V-4)個)…１ ０…((V-1)個)…０
の形になると言える。ここでVは正整数、頂点数を2Vとしている。
これと最初のビットが１になるグループとの和はやはり最初のビットが１になるのグループに入り、
１０１０１ １…((V-2)個)…１ ０…((V-2)個)…０ ｘ…((V-1)個)…ｘ
の形になる。
※なお、上の表現はビットの位置というよりビットの個数に重点を置いて表現している。このあたりはいずれより分かりやすい表現ができたらと思う。
ここで、最初のビットが１になるグループのベクトルは、全て、１の数が2V個よりも少なくなければならない（全ての頂点を通る時は最初のビットは０となるため）事から、最初のビットが１となる最短のサイクルは(V+1)という事になる。
〔註：今書いてて気付いたが、必ずしも単一のサイクルであるとは限らないので、この議論は不充分であったorz〕
〔註：サイクル全ての辺の合計の最小値が(V+1)個なので、これは不可分なサイクル、すなわち単一のサイクルと言える〕
このようなグラフはほとんど自明で、少なくとも平面グラフでは（一つの辺に必ず二つの面が存在するため）全ての頂点を通る時に決して通らない辺というものは存在しないと思われる。
全ての頂点を通る時に必ず通る辺
このような辺があっても３彩色できないため、これも条件を確かめておく必要があるが、意外にも“決して通らない辺”の時よりも難しい問題である。
まず、その辺の両端に接続する４つの辺のうち一つが存在しない場合を考えと、それは「全ての頂点を通る時に存在しない辺」となるため、前項の議論に帰着する。
次に、その辺が存在しない場合にその辺の両端に接続する４つの辺が全て存在する場合を考えると、この場合にはその辺（とその両端の頂点）が存在しない３正則グラフに帰着し、それが全ての頂点を通らないグラフになるため、４正則グラフに縮約できない。このようなグラフは樹状構造を持つので。元のグラフにもカットエッジが存在する事になり、矛盾を導ける。
※他にも細かい説明が必要だがそれらは省く。いずれ補足したい。
同一の成分からなるベクトルの構成
〔追記：註：以下の議論は誤りでした〕
部分空間の元は、頂点辺行列の各列ベクトルの線形結合の係数をベクトルで表したものと考える事ができる（線形結合の和は常に0である事に注意）。
そこで、部分空間の全ての元を列挙し、各成分のみを取り出して並べたベクトルの集合（または、等号という自明な同値関係による同値類）を考える。ベクトルの次元は部分空間の元の総数である。今、前提条件として、部分空間全体を通じて共通して0となる成分は存在しないため、この集合のベクトルには零ベクトルは存在しない。また、部分空間自体が位数２の体上で定義されているため、どのベクトルも、1となる成分と0となる成分は同数となる。以降、このベクトルを係数ベクトルと呼ぶ事にする。
頂点辺行列の各行の1となる三つの要素は各係数ベクトルにどう配分されるか
係数ベクトルは一つのベクトルというより、線形結合の係数のうち同一になるものを一つにまとめたものであって、等号という自明な同値関係によって類別された同値類と考える事ができる。
したがって、頂点辺行列から見た場合、各行にちょうど三つずつ1となる要素を、各係数ベクトルに配分するように見える。どのように配分しても、線形結合の和が0であるように配分されなければならない。
一つの係数ベクトルのみに、1が三つ全てが配分される事はない
なぜならば、係数ベクトルに零ベクトルは存在しないため、必ず線形結合の和に1が表れてしまうからである。
二つの係数ベクトルに、1が三つ配分される事もない
つまり、一つの係数ベクトルに1が二つ、残りの係数ベクトルに1が一つ配分される場合、前の係数ベクトルの値と無関係に、後ろの係数ベクトルは0でなければならないから、これは零ベクトルであり、前提に反する。
三つの係数ベクトルに、1が一つずつ配分される場合
つまり、三つの係数ベクトルのうち、同時に1になれるのはちょうど二つずつで、以下のような組合せとなる：
- {0,0,0}
- {1,1,0}
- {1,0,1}
- {0,1,1}
この係数ベクトルの組合せは、見ての通り、ともに0となる成分が存在しない相異なるベクトルを含んでいる。
相異なる係数ベクトルは四つ以上存在しない
〔追記：註：いえ、存在します。勘違いです。〕
これは元の３正則グラフが連結である事から導かれる：ある行で線形結合の和が0でも、連結な別の行では線形結合の和が0にならないような係数が必ず存在するため（もし同じならば、相異なるという条件か、零ベクトルが存在しないという前提に反する）。
なお、元のグラフが連結でない場合でも、部分空間が群である事から、グラフの各コンポーネント毎に別々に適用して、それら全ての和を考えれば良いので、一般性は失わない。つまり連結なグラフについてのみ論じても題意に反しない。
結論
〔追記：註：この記事での証明は現段階で失敗しており、誤りです。〕
この一連の議論を順に振り返る：
- 地図の四色問題は、地図の境界線を３正則グラフ化する事で、３正則グラフの辺３彩色問題に帰着される。
- ３正則グラフの辺３彩色は、位数２の体上で頂点辺行列を考える事で、簡素な連立方程式として表す事ができる。
- ループを持たない３正則グラフが辺３彩色できる必要十分条件は、グラフにカットエッジ、すなわちいかなるサイクルにも属さない辺が存在しない事である。
特に最後の定理は、平面グラフでなくとも成立する、より広い一般的な真理であると言える。
これを前の議論で見たように平面グラフの四色問題にあてはめると、機械的なグラフの変形によって、自然に四色定理が導かれる。したがって、四色定理は、今回証明したより広い範囲で成立する定理から導かれる系であるという事ができるのではないだろうか。
〔追記：註：この記事での証明は現段階で失敗しており、誤りです。〕
今回の議論はいくらか厳密性を欠いているため、これが正しい議論だと言うには、もっと詳しく査読する必要であると思う。しかし全体を通して、どんなに難しいと言っても大学教養レベルの数学の知識で理解する事ができると思う。工夫すれば、高校生はもちろん、中学生や、考え方自体は小学生でも理解できるのではないかと思う。
余談
これは、自分で四色問題を解いてみようと思ったきっかけ。これ、2014年か…
q.hatena.ne.jp
