■平面グラフの頂点彩色(その6)

オイラーの多面体定理で示される制限からいえることとして,

  F=f3+f4+f5+・・・

  2E=3f3+4f4+5f5+・・・

  6F−2E≧12

に代入すると

  3f3+2f4+f5−f7−2f8−3f9−・・・≧12

 地図のように2つの辺に囲まれた領域まで許すことにすると,この数え上げ公式は

  4f2+3f3+2f4+f5−f7−2f8−3f9−・・・=12

となります.いずれにせよ,係数が1ずつ小さくなり,それが0となるf6は式中に現れません.

 このことから,f3,f4,f5の少なくとも1つは0でない→多面体には3角形か4角形面か5角形面が少なくとも1つなければならない,同様に,多面体の少なくとも1つの頂点は3次か4次か5次でなければならない→すべての頂点の次数が6以上となることは不可能であり,必ず次数が5以下の頂点をもつことが導き出されます.これもオイラーが知っていた結果であるということです.

 ここで,

(1)f2=f3=f4=0だとすると,少なくとも12個のf5がなければならないことになる

(2)多面体の面がすべてf5とf6であるならば,f5=12(切頂二十面体)

(3)多面体の面がすべてf4とf6であるならば,f4=6(切頂八面体)

(4)多面体の面がすべてf4,f6,f8であるならば,f4=f8+6(斜方切頂立方八面体)

これらの結果は極めて重要で,四色定理の証明の中核をなしています.

===================================