2015/07/23

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

分野: グラフ理論  レベル: 数学オリンピック

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

四色定理について

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

四色定理
  • 図は非常に単純な例ですが,地図がどんなに複雑でも四色で塗れる!というのが四色定理です。主張が非常にシンプルで美しいため有名な定理です。
  • 証明は非常に複雑(コンピュータを使った力技が必要)です。一方,五色定理(四色定理の主張の「四色」を「五色」に変えた弱い定理)は証明が一気に簡単になり,高校生でも理解できます。というわけで,この記事では五色定理の証明を解説します。

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

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

  • $G$ の頂点は地図の面に対応。
  • 地図で隣接している面同士に枝を引く。
五色定理の証明の準備

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

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

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

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

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

補題:平面グラフには次数(隣接する頂点数)が $5$ 以下の点が必ず存在する。

証明

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

各頂点に $6$ 本以上枝が集まるので,$6|V|\leq 2|E|$
各面の境界に含まれる枝数は $3$ 以上なので $3|F|\leq 2|E|$

これらの不等式とオイラーの多面体定理より,
$2=|V|-|E|+|F|\\
\leq \dfrac{1}{3}|E|-|E|+\dfrac{2}{3}|E|\
=0$
となり矛盾。背理法により補題が示された。

五色定理の証明

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

証明

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

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

・ $v$ の次数が $5$ であり,その $5$ つの頂点が全て異なる色で塗られている場合:
$5$ つの頂点を $v_1,\cdots, v_5$ とし,各頂点の色を $c_1,\cdots,c_5$ とする。
$v_1$ から色 $c_1$ と $c_3$ で塗られた頂点のみをつたって行ける頂点の集合を $V_{13}$ と書く。

五色定理の証明

CASE1:$v_3\not\in V_{13}$ のとき,
$V_{13}$ の色 $c_1$ と $c_3$ をひっくり返せば彩色の条件を保ったまま $v$ の周りを四色にできる。 $v$ を $c_1$ で塗ればよい。

CASE2:$v_3\in V_{13}$ のとき,
$v_1$ から $v_3$ に $c_1$ と $c_3$ で塗られた頂点のみからなる道が存在する。
これと $G$ の平面性から,$v_2$ から $v_4$ に $c_2$ と $c_4$ で塗られた頂点のみからなる道は存在しない。
つまり,$v_2$ から色 $c_2$ と $c_4$ で塗られた頂点のみをつたって行ける頂点の集合 $V_{24}$ の色 $c_2$ と $c_4$ をひっくり返せば $v$ の周りが四色になる。 $v$ を $c_2$ で塗ればよい。

・そうでない場合:
余った色で $v$ を塗ればよい。

四色と言えば迷わず赤黄青緑ですが,五色目を何色にするか迷いました。
分野: グラフ理論  レベル: 数学オリンピック