平面グラフの隣接するどの２頂点も異なる色で彩色することを考えます。

平面グラフでは４色定理「任意の平面グラフは４色以下で彩色可能である」ことが証明されているのですが、ここでは、オイラーの公式の応用として、「６色以下で彩色可能」であることを示します。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

V=Σvi,E=Σei,F=Σfiとおきます。各頂点の次数を考えるとΣd(vi)=2E,Σd(fi)=2E・・・握手定理

オイラーの定理V-E+F=2の両辺を-6倍します。

-12=-6V+6E-6F

=(-6V+Σd(vi))+2(2Σd(fi)-6F)

=Σ(d(vi)-6)+Σ(2d(fi)-6)

２角形はあり得ないので、すべての面で2d(fi)-6＞=0

したがって、ある頂点でd(vi)-6＜0

すなわち、任意の平面グラフには次数が５以下の頂点が存在することになります

任意の平面グラフは６色以下で彩色可能であると仮定します（帰納法）。

６頂点以下の場合は自明

任意の平面グラフには次数が５以下の頂点が存在するので、この頂点ｖを取り除いた平面グラフに対しても６色以下で彩色可能です

隣接する頂点は5個以下であるため、その頂点たちに使われていない色でｖを彩色できるというわけです。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝