四色定理、五色定理

四色定理は、「平面上の地図は、四色で塗り分けられる」という定理です。

1975年に証明されましたが、コンピューターが必要な複雑な証明なので、ここでは理解しやすい五色定理について述べます。

次のような図の塗り分けを考えます。

図の各面を点で表し、面が隣り合う場合には点と点を結ぶことにすると、次のようなグラフに置き換えられます。（グラフ理論でいうグラフは、点の集合と辺の集合で表されます。例：路線図、電気図など）

辺の両端の点をそれぞれ異なる色に塗り分けて元の図に戻すと、この図の場合は三色に塗り分けられることがわかります。

五色定理

「平面グラフは五色に塗り分けられる」

【前提条件】
オイラーの公式

多面体の頂点、辺、面の個数をそれぞれ、\(v,e,f\)とすると\(v-e+f=2\)

不等式　\(e \leq 3v-6\)の証明

辺を基準にすると、のべ面数は\(2e\)
各面の辺数は、3以上なので　\(2e\geq 3f\)

オイラーの公式から、\(e\leq3v-6\)　　（A)

【グラフに関する定理】
平面グラフには次数5以下の点が必ず存在する　（B)

証明
全ての頂点が次数6以上（6本以上の辺が出ている）とすると、
\(6v\leq2e\)　つまり　\(3v\leq e\)で、（A)の不等式\(e\leq3v-6\)に矛盾する

五色定理の証明

平面グラフ\(G\)が、五色に塗り分けられることを\(v\)に関する数学的帰納法で証明します。

\(v\leq5\)のときは自明、\(v=k\)のときを仮定して、\(v=k+1\)を証明します。

（B)により、\(G\)には次数5以下の頂点が存在するので、そのうちの一つを\(v_0\)とします。

①\(v_0\)の次数が4以下の場合
\(v_0\)に塗る色を、隣接する頂点とは違う色にできるのでOK

②\(v_0\)の次数が5の場合
\(v_0\)に隣接する5頂点が4色で塗られているなら、\(v_0\)を5色目で塗ればいいいので、5色に塗られているケースを考えます。

グラフ\(G\)から\(v_0\)を取り除いたグラフ\(G’\)は、帰納法の仮定により五色に塗り分け可能です。
頂点を\(v_1\)、・・・、\(v_5\)、それぞれの色を\(c_1\)、・・・、\(c_5\)とします。

\(c_1\)または\(c_4\)で塗られた頂点と、それらを接続する辺だけを取り出した部分グラフを\(G_1{}_,{}_4\)とします。

\(v_4 \notin G_1{}_,{}_4\)　なら

\(v_4\)の色を\(c_1\)にして\(v_０\)を\(c_4\)に塗れば、塗り分け完了です。

\(v_4 \in G_1{}_,{}_4\)　なら

今度は、グラフ \(G’ \)から\(c_2\)または\(c_5\)で塗られた頂点とそれらを接続する辺だけを取り出した部分グラフ\(G_2{}_,{}_5\)について同様に考えます。このとき、\(v_5 \notin G_2{}_,{}_5\)か\(v_5 \in G_2{}_,{}_5\)のどちらかですが、後者はありえません。部分グラフ\(G_1{}_,{}_4\)の辺と、どこかで交わるからです。
従って、\(v_5\)の色を\(c_2\)にして、\(v_０\)を\(c_5\)に塗れば塗り分け完了。