■平面グラフの頂点彩色(その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以下の頂点をもつことが導き出されます.これもオイラーが知っていた結果であるということです.

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