■平面グラフの頂点彩色(その5)
正則とは限らない一般の多面体では
Σpi=p1+・・・+pf=2e,
Σqi=q1+・・・+qv=2e
となります.pi≧3,qi≧3ですから
2e≧3f,2e≧3v
このことから多面体は7本の辺をもつこと(e=7)は不可能であることが証明されます.
(証)e=7なる多面体が存在したと仮定すると,3f≦14,3v≦14.f,vは面,頂点の個数なので,3より大きな整数でなければならない.したがって,f=4,v=4,e=7となるが,これはオイラーの多面体定理
v−e+f=2
を満たさないので矛盾が生じる.
このことから
f≧4,v≧4,e≧6(e≠7)
であることがわかりましたが,他にオイラーの多面体定理で示される制限はないのでしょうか?
v−e+f=2,2e≧3f,2e≧3v
を組み合わせると,
2v+2f=2e+4≧3f+4 → f≦2v−4
2v+2f=2e+4≧3v+4 → v≦2f−4
これらはシュタイニッツの定理(1906年)と呼ばれますが,オイラー自身すでに
f≦2v−4,v≦2f−4
という結果を知っていたようです.
また,別の組合せ方をすると,
3v+3f=3e+6≦2e+3f → 3f−e≧6
3v+3f=3e+6≧2e+3v → 3v−e≧6
も得られます.
===================================
つぎに,3次元立体では必ず頂点に結合する辺の個数が3の頂点か3角形の面をもつことを示します.n本の辺をもつfn枚の面とn本の辺が交わるvn個の頂点をもつ凸多面体について,
i)Σnfn=Σnvn
ii)Σf2n+1は偶数
iii)v3+f3>0
を順に示していきます.
(証)各辺は2個の頂点をもつから,Σnvn=2E.また,各辺では2枚の面が交わるからΣnfn=2E.
(証)i)より,Σ(2n+1)f2n+1=(偶数),したがって,Σf2n+1も偶数.
(証)E=Σen,V=Σvn,F=Σfn,Σnfn=Σnvn=2E. もしv3=0,f3=0ならば,2E=4v4+5v5+・・・≧4V.同様に,2E≧4F.これより,V−E+F≦E/2+E/2−E=0.これはオイラーの多面体定理:V−E+F=2に矛盾するから,v3,f3のうち,少なくとも1つは0でない.
さらに,オイラーの多面体定理で示される制限からいえることとして,
F=f3+f4+f5+・・・
2E=3f3+4f4+5f5+・・・
を
6F−2E≧12
に代入すると
3f3+2f4+f5−f7−2f8−3f9−・・・≧12
このことから,f3,f4,f5の少なくとも1つは0でない→多面体には3角形か4角形面か5角形面が少なくとも1つなければならない,同様に,多面体の少なくとも1つの頂点は3次か4次か5次でなければならない→すべての頂点の次数が6以上となることは不可能であり,必ず次数が5以下の頂点をもつことが導き出されます.これもオイラーが知っていた結果であるということです.
===================================