ここ一年くらい、そんな事ばかり考えてるわけだけども。
3正則グラフからのアプローチは一旦少し諦めて、ケンプの証明にここまでの知見を活かしてみる事を考える。
まず(僕の思い違いでなければ)ケンプによれば、どんな地図にも、2辺国、3辺国、4辺国、5辺国、6辺国、のいずれかが必ず含まれている事になっている。たぶん、オイラーの多面体定理から導かれるのだと思うが、いずれ自分でも証明してみたい。
一方、国の数を変えずに、頂点を引き剥がす事によって、境界線を全て3正則化できる事はすでに示した。
以上から、3正則化しても、やはり地図には2~6辺国5辺国のいずれかが含まれる事になるわけで、この3正則化した地図のみを使ってケンプのアプローチを行っても何の問題もない。
次に、ここまでに得た知見で、4彩色可能な地図の性質を明らかにしてみる。
まず、全ての頂点を通り、辺の数が偶数であるようなサイクルの組が存在すれば、4彩色可能になる事はすでに示した。
が、これは3正則グラフ、つまり全ての頂点の次数が奇数(奇点という)の場合であって、3正則でない場合にはどうであろうか。
結論から言えば、頂点の次数が偶数(偶点という)の場合は通る必要がない事がわかる。
まとめると、境界線に「奇点を偶数回通るようなサイクルの組で、全ての奇点を通るサイクルの組」が存在すれば、地図は4彩色できる。
(註:「偶数回通る」だけではだめでした。ただ4彩色可能かどうかを証明するためだけならここは実は重要ではないので、細かい条件は後回しにしようorz)
ケンプのアプローチでは、帰納法を使うにあたり、増えた国の回りの国の彩色を変更する事で対応しようとしたけれど、それだと証明に必要な地図の形(不可避集合と呼ぶそうだ)が600以上にも膨れ上がるという欠点があった。この一つ一つを証明するのにコンピューターを使う必要があり、「(エレガントではないので)エレファントな証明」と揶揄する人もいたわけだ。
じゃあ境界線に着目すれば少なくて済むのだろうか。
実のところ、思ったより場合分けが必要になるので、それほどエレガントにはならないのかもしれないが、少し試してみた感触として、手作業で作業ができる程度には簡略化されるような気はしている。
例えば、(2辺国、3辺国は証明が簡単なので省くとして)5辺国の場合には調べるべき国の形は1種類しかない事がすぐにわかっている。
一方で、4辺国でもただちに証明できないものが一つ存在する事がわかっているし、6辺国ではさらに増えるであろう事が容易に想像される。
まあ、こういう事は気長にやっていくとしようか。
(追記)
3正則平面グラフに於いては、2辺国、3辺国、4辺国、5辺国のいずれかが必ず含まれます。全ての面が6辺国以上となる3正則平面グラフは存在しません(証明はわりと簡単)。
(追記)
少し検討した結果、次のようになった:
- 2辺国:1通り
- xx
- 3辺国:1通り
- xyz
- 4辺国:3通り
- xxxx
- xxyy
- xyxy
- 5辺国:2通り
- xxxyz
- xxyxz
6辺国:9通りxxxxxxxxxxyyxxxyxyxxyxxyxxyyzzxxyzyzxxyzzyxyzxzyxyzxyz
これら計16通り7通りについて調べれば充分なはず。不可避集合を検討するよりもずっと少なくて済むと思われる。
(註:書いてから気付いたけど、これにさらに連結なサイクルかどうかで場合わけしなければならない可能性があるので、実際に検討する組み合わせは実はもっと多いですorz)
(追記)5辺国の最後のパターンで、ケンプが直面したのと同じ問題に直面orz。4辺国までがあまりに単純だったので油断した。