四色定理の紹介と五色定理の証明

四色定理

任意の地図は四色で塗り分けることができる。

四色定理について

  • 地図の各領域に色を塗りたい,そのとき隣り合う領域は同じ色にはしたくないという状況を考えます。アメリカの本土とアラスカのような飛び地は考えません,一つの面を一つの色で塗ります。 四色定理

  • 図は非常に単純な例ですが,地図がどんなに複雑でも四色で塗れる! というのが四色定理です。主張が非常にシンプルで美しいため有名な定理です。

  • 証明は非常に複雑(コンピュータを使った力技が必要)です。一方,五色定理(四色定理の主張の「四色」を「五色」に変えた弱い定理)は証明が一気に簡単になり,高校生でも理解できます。というわけで,この記事では五色定理の証明を解説します。

準備:平面グラフの頂点彩色に帰着

与えられた地図に対して,以下のようなグラフ GG を構成します(→グラフ理論の基礎)。

  • GG の頂点は地図の面に対応。
  • 地図で隣接している面同士に枝を引く。

五色定理の証明の準備

そして「隣接する領域が異なる色になるように,五色で地図の面を塗る」という当初の目標を「どの枝の両端点も異なる色になるように,五色で GG の頂点を塗る」と言い換えます。

GG が平面的グラフ(平面に交差なしで書けるグラフ,→平面グラフ・平面的グラフの意味とオイラーの定理の応用)になることに注意すると,以下の定理を証明すればよいことが分かります。

定理

平面的グラフは五彩色可能(五色あればどの枝の両端点も異なる色になるように頂点を塗れる)。

準備2:次数5以下の頂点の存在

五色定理の証明の準備その2です。

補題

平面的グラフには次数(隣接する頂点数)が 55 以下の点が必ず存在する。

証明

平面的グラフ GG の全ての頂点の次数が 66 以上と仮定する。GG の頂点数,枝数,面の数をそれぞれ V,E,F|V|,|E|,|F| とする。

各頂点に 66 本以上枝が集まるので,6V2E6|V|\leq 2|E|

各面の境界に含まれる枝数は 33 以上なので 3F2E3|F|\leq 2|E|

これらの不等式とオイラーの多面体定理より,

2=VE+F13EE+23E=02=|V|-|E|+|F|\\ \leq \dfrac{1}{3}|E|-|E|+\dfrac{2}{3}|E|=0

となり矛盾。背理法により補題が示された。

五色定理の証明

以上の準備をふまえ,平面的グラフ GG が五彩色可能であることを V|V| に関する帰納法で証明します。

証明

V=1|V|=1 のときは自明。以下,V=k|V|=k のときを仮定して V=k+1|V|=k+1 のときを証明する。

GG には補題より次数 55 以下の頂点が存在する,そのうちの一つを vv とする。GG から vv (および vv に接続する枝)を除いたグラフを GG' とする。帰納法の仮定により GG' は五彩色可能である。この彩色で GGvv 以外の頂点を塗る。

(i) vv の次数が 55 であり,その 55 つの頂点が全て異なる色で塗られている場合:

55 つの頂点を v1,,v5v_1,\cdots, v_5 とし,各頂点の色を c1,,c5c_1,\cdots,c_5 とする。

v1v_1 から色 c1c_1c3c_3 で塗られた頂点のみをつたって行ける頂点の集合を V13V_{13} と書く。

五色定理の証明

CASE1: v3∉V13v_3\not\in V_{13} のとき,

V13V_{13} の色 c1c_1c3c_3 をひっくり返せば彩色の条件を保ったまま vv の周りを四色にできる。 vvc1c_1 で塗ればよい。

CASE2: v3V13v_3\in V_{13} のとき,

v1v_1 から v3v_3c1c_1c3c_3 で塗られた頂点のみからなる道が存在する。

これと GG の平面性から,v2v_2 から v4v_4c2c_2c4c_4 で塗られた頂点のみからなる道は存在しない。

つまり,v2v_2 から色 c2c_2c4c_4 で塗られた頂点のみをつたって行ける頂点の集合 V24V_{24} の色 c2c_2c4c_4 をひっくり返せば vv の周りが四色になる。 vvc2c_2 で塗ればよい。

(ii) そうでない場合:

余った色で vv を塗ればよい。

四色と言えば迷わず赤黄青緑ですが,五色目を何色にするか迷いました。