五色定理

基底段階。$G$ の頂点数が5以下なら、各頂点に異なる色を与える。使う色は高々5色なので主張は成り立つ。

帰納段階の準備。頂点数が $n$ 未満の任意の平面グラフが5彩色可能であると仮定し、$G$ を $n$ 頂点の平面グラフとする。任意の単純平面グラフは $E \le 3V - 6$ を満たす(この辺数の上界はオイラーの公式から証明される)ので、次数の総和は高々 $2(3n-6) = 6n-12$、すなわち $6n$ より小さい。したがって平均次数は6未満であり、次数が高々5であるような頂点 $v$ が存在する。

$v$ を除くと $n-1$ 頂点のより小さな平面グラフが得られ、帰納法の仮定によりそれは正当な5彩色を持つ。$v$ の隣接頂点が高々4個であれば、それらは高々4色しか使っていないので、$v$ に使える色が一つ残り、証明が終わる。

残る場合は deg$(v) = 5$ であり、$v$ の5個の隣接頂点にちょうど1回ずつ5色すべてが現れる場合である。平面上の描画で $v$ の周りに現れる巡回順に隣接頂点を第一、第二、第三、第四、第五と呼び、それぞれ色1、2、3、4、5が塗られているとする。色1または3の頂点全体からなる部分グラフ $H_{1,3}$ を考える。第一の頂点と第三の頂点が $H_{1,3}$ の異なる連結成分にあるなら、第一の頂点を含む成分全体で色1と3を入れ替える。これは色1または3の頂点にしか触れないので正当な彩色のままであり、第一の頂点は今や色3となるため、色1が $v$ に使える。

そうでなければ第一の頂点と第三の頂点は $H_{1,3}$ の同じ連結成分にあり、色1と3が交互に現れる道で結ばれている。この道は $v$ および第一・第三の頂点への二本の辺とともに、平面内で閉曲線をなし、(ジョルダン曲線定理により、$v$ の周りの巡回順が第一、第二、第三、第四、第五であることから)第二の頂点と第四の頂点を分離する。したがって色2と4が交互に現れる道は第二の頂点と第四の頂点を結ぶことができない。なぜならそのような道は色1-3の閉曲線を横切らねばならないからである。そこで第二の頂点を含む $H_{2,4}$ の成分全体で色2と4を入れ替える。これにより色2が $v$ に使えるようになる。

いずれの場合も $v$ はどの隣接頂点とも衝突せずに5色のうちの一つを受け取り、$G$-v の彩色を $G$ 全体に拡張できる。帰納法により、任意の平面グラフについて $\chi(G) \le 5$ が成り立つ。