四色定理の証明は難しいので妥協して五色定理を証明しよう

四色定理というのは、どんな地図も4色以下の色で塗り分けられる、という定理です。塗り分けということなので、辺で接している領域は違う色で塗る、というルールで塗ります。以下に2つ例を示します。

 :20180718131813j:plain

上の例だと3色(青、黄色、赤)で塗り分けられています。

 :20180718132000j:plain

上の例だとちょっと複雑になっていて4色(青、黄色、赤、肌色)なければ塗り分けができません。

 

さて、地図というのはいくらでも複雑なものが作れますから、複雑さに応じて、塗り分けのためにたくさんの色が必要になりそうな気がします。しかしその直感に反して、実は4色あれば十分である、ということが知られています。これが四色定理と呼ばれる事実で、証明されたのは1976年、アッペルとハーケンという人によってです。

 

4色定理は、通常平面グラフによって考察されることが多いです。いま、地図上の領域の大きさや形は塗り分けの話には関係がなく、各領域が接している・接していないという情報だけが必要です。ということで、各領域を頂点、接している領域同士を辺で結ぶ、という約束でどんな地図でも平面グラフに書き換えられます。つまり、地図の塗りわけ問題は、平面グラフを考察すれば良いのです。

 :20180718131829j:plain  :20180718131823j:plain

平面グラフ \displaystyle G の頂点に、隣接する頂点の色は異なるように、色をつけることを彩色といい、グラフ \displaystyle G  \displaystyle n 色以下で彩色できるとき、グラフ \displaystyle  G \displaystyle n-彩色可能であるといいます。平面グラフの彩色が地図の塗り分けに対応しているわけですね。

 

平面グラフの言葉を使うと、先述の四色定理は次のようにいうことができます。

 

任意の平面グラフは \displaystyle 4- 彩色可能である。

今のところ、四色定理を簡単に証明する方法は見つかっていないはず(多分)。ということで少し妥協して、次の五色定理を証明しようと思います。以前の記事で紹介して、任意の平面グラフには次数が5以下の頂点が存在する、という事実を使います。証明は以下の記事をご覧ください。

平面グラフには次数が5以下の点が必ず存在する – 数学と高校教師

 

 

五色定理(四色定理の妥協版)

任意の平面グラフは \displaystyle 5- 彩色可能である。

(証明)

平面グラフ G に対し、頂点数 n に対する帰納法を使う。頂点数が 5 以下の場合には各頂点に違う色をそれぞれ塗ることで 5- 彩色可能であることがわかる。頂点数が n-1 以下のときに定理が成り立つとする。平面グラフには次数が5以下の頂点 x が存在する。帰納法の仮定により、 G から頂点 x (とそれに隣接する辺)を取り除いたグラフ G-x  5- 彩色可能である。もし x の次数が4以下であれば、隣接する頂点に塗られた色と別の色を x に塗ることで G の5-彩色が完了する。そこで x の次数は5であるとしよう。

 

 x に隣接する頂点を時計回りに y_1,y_2,y_3,y_4,y_5 とする。これらの5頂点に塗られている色が4色以下であれば、使われていない色を x に塗ることで G  5- 彩色が完了する。そこで、 y_1,y_2,y_3,y_4,y_5 にすべて異なる色 1,2,3,4,5 が塗られているとしよう。

 

ここで、記述を簡略化させるために「(1,3)ケンペ鎖」という考えを導入する。(1,3)ケンペ鎖とは、 G の頂点で、色1と3が塗られているものと、それらの間を結ぶ辺だけを集めてできるグラフのことである。ここからは y_1 からでている(1,3)ケンペ鎖が、 y_3 を含むかどうかで場合分けを行う。

 :20180718151136j:plain

 

(ケース1) 頂点 y_1 から出ている(1,3)ケンペ鎖が y_3 を含まない場合。そのケンペ鎖の頂点について、色 1のものは色 3 に、色 3 のものは色 1 に塗り替えても、グラフ G-x  5- 彩色となっている(塗り分けが維持できている)。そして y_1 は色3になっているので、 x に色1 を塗ることができ、グラフ G  5- 彩色が完成する。

 

(ケース2)頂点 y_1 から出ている(1,3)ケンペ鎖が y_3 を含む場合。このとき、 y_2 が(1,3)ケンペ鎖で囲まれた状態になっている(下図の赤部分)。

 :20180718143913j:plain

ここで y_2 から出ている(2,4)ケンペ鎖を考えると、(1,3)ケンペ鎖が壁になっているせいで y_4 には到達できない。よってこの(2,4)ケンペ鎖の頂点で色2のものは色4に、色4のものは色2に塗り替えても、グラフ G-x  5- 彩色となっている。そして y_2 は色4になっているので、 x に色2 を塗ることができ、グラフ G  5- 彩色が完成する。(証明終)

 

 

毎度ですが、グラフ理論は難しい予備知識があまり必要なく、理詰めで考えていけるのが面白いですね。

では、今回はこの辺で。