📂グラフ理論

五色定理の証明

証明

戦略：数学的帰納法を使用する。$n-1$個の頂点を持つシンプルな平面グラフが全て$5$-彩色可能だと仮定した場合、頂点がもう1つ多くても同じく$5$-彩色可能であることを示す。

---

$n-1$個の頂点を持つシンプルな平面グラフが全て$5$-彩色可能だと仮定しよう。

シンプル平面グラフの性質 [2]: 任意のシンプル平面グラフ$G$は$\deg v \le 5$である頂点$v \in V(G)$を持つ。

$G$がその性質により$n$個の頂点を持つ場合、$\deg v \le 5$である$v \in V(G)$が存在する。この$v$が$5$-彩色可能性に問題を引き起こさなければ、$v$の抜けたグラフ$G - v$は$n-1$個の頂点を持つので$5$-彩色可能であり、$G$も$5$-彩色可能である。

もし$\deg v < 5$なら、$v$の彩色は何でも構わない。

もし$\deg v = 5$なら、$v$に隣接する頂点を$v_{1} , \cdots , v_{5}$とし、$v$の色を$c$とする。

クラトフスキーの定理: グラフが平面グラフであることと、その部分グラフが$K_{5}$や$K_{3,3}$にホメオモルフィックなものがないことは同値である。

$G$は平面グラフなので、$v_{1} , \cdots , v_{5}$は部分完全グラフ$K_{5}$を形成してはいけない。従って、これらの少なくとも2つの頂点は隣接してはいけない。一般性を失わずに、これら2つの頂点を$v_{1} , v_{2}$とする。$vv_{1}$と$vv_{2}$を収縮して得られるグラフは$n-2$個の頂点を持つので$5$-彩色可能である。今、収縮していたグラフの$v_{1}$と$v_{2}$を元に戻しつつ、$c$で彩色すると、$v$は$c$を含め最大で$4$種類の異なる色の頂点と隣接できるので、残った色の一つを選んで彩色することにより、$5$-彩色を行うことができる。

■