■平面グラフの頂点彩色(その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(斜方切頂立方八面体)
これらの結果は極めて重要で,四色定理の証明の中核をなしています.
===================================