証明のアウトライン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/20 08:01 UTC 版)
まず、与えられた地図に単純な平面グラフ G {\displaystyle G} を対応させる。つまり、地図の各領域をグラフの頂点とし、2領域が隣接しているときかつそのときに限り、対応する2頂点を1つの辺で結ぶものとする。こうして問題はグラフの彩色問題に変換される：各頂点に色を塗って、どの辺についても端点である2頂点の色が一致しないようにできるか。 グラフ G {\displaystyle G} は単純平面グラフである、つまり平面上にどの2辺も交差させることなく描くことができ、かつどの2頂点間にも2本以上の辺が存在せず、ループも存在しないので、平面のオイラー標数を用いることで、グラフ G {\displaystyle G} には最大でも5本の辺によってしか接続されていないような頂点が存在することが証明できる（注意：五色定理の仮定（色の数が最大で5）が使われるのはこの箇所だけである。もし同じ手法で四色定理を証明しようとしても、この段階で頓挫する。実際、正二十面体グラフ（icosahedral graph）は5-正則な平面グラフであり、接続する辺が4本以下であるような頂点は存在しない）。このような頂点を1つ選んで v {\displaystyle v} と呼ぶことにする。 今、頂点 v {\displaystyle v} を G {\displaystyle G} から取り除く。このようにして得られるグラフ G ′ {\displaystyle G'} は頂点の数がグラフ G {\displaystyle G} よりも1個だけ少ないので、数学的帰納法により5色で彩色できるとしてよい。頂点 v {\displaystyle v} は他の5個の頂点と隣接しているとする（4個以下であれば、隣接する頂点に使われていない色を塗ることでグラフ G {\displaystyle G} の彩色は終わる）。そこでこれらの v {\displaystyle v} と隣接していた5頂点を（反）時計回りに v 1 {\displaystyle v_{1}} , v 2 {\displaystyle v_{2}} , v 3 {\displaystyle v_{3}} , v 4 {\displaystyle v_{4}} , v 5 {\displaystyle v_{5}} とする（番号の振り方は G {\displaystyle G} の描き方に依る）。もしこれらが5つの異なる色で塗られていなければ、明らかに頂点 v {\displaystyle v} を使われていない色で塗ることでグラフの彩色が終わる。 そこで、頂点 v 1 {\displaystyle v_{1}} , v 2 {\displaystyle v_{2}} , v 3 {\displaystyle v_{3}} , v 4 {\displaystyle v_{4}} , v 5 {\displaystyle v_{5}} はそれぞれ色 1, 2, 3, 4, 5 で塗られていると仮定する。 グラフ G ′ {\displaystyle G'} から、色1または3で塗られた頂点と、それらを接続する辺だけを取り出した部分グラフ G 1 , 3 {\displaystyle G_{1,3}} を考える。明らかにどの辺も色1の頂点と色3の頂点を結ぶ（これをケンプ鎖（英語版）という）。もし v 1 {\displaystyle v_{1}} と v 3 {\displaystyle v_{3}} とがグラフ G 1 , 3 {\displaystyle G_{1,3}} の異なる連結成分に属するならば、 v 1 {\displaystyle v_{1}} が属す連結成分で色1と色3を交換することで、頂点 v {\displaystyle v} を色1で塗ることができるようになり、証明が終わる。 そうでない場合、 v 1 {\displaystyle v_{1}} と v 3 {\displaystyle v_{3}} とはグラフの同一の連結成分に属すことになるので、色1と色3の頂点のみを伝ってこれらを結ぶ G 1 , 3 {\displaystyle G_{1,3}} の道を見つけることができる。 ここで今度は、グラフ G ′ {\displaystyle G'} から色2または4で塗られた頂点とそれらを接続する辺だけを取り出した部分グラフ G 2 , 4 {\displaystyle G_{2,4}} に目を向け、同じ議論を繰り返すことにする。すると、グラフ G 2 , 4 {\displaystyle G_{2,4}} の v 2 {\displaystyle v_{2}} を含む連結成分において色2と色4を交換することで頂点 v {\displaystyle v} が色2で塗れるようになるか、色2と色4の頂点のみを伝って v 2 {\displaystyle v_{2}} と v 4 {\displaystyle v_{4}} を結ぶ G 2 , 4 {\displaystyle G_{2,4}} の道を見つけることができるかの、二つに一つである。ところが後者はあり得ない。なぜならそのような道は、既に見出した「色1と色3の頂点のみを伝って v 1 {\displaystyle v_{1}} と v 3 {\displaystyle v_{3}} を結ぶ道」とどこかで交わらざるを得ないからである。 以上でグラフ G {\displaystyle G} が5色で塗り分けられることが判明した。
※この「証明のアウトライン」の解説は、「五色定理」の解説の一部です。
「証明のアウトライン」を含む「五色定理」の記事については、「五色定理」の概要を参照ください。
- 証明のアウトラインのページへのリンク
