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

【1】トーラス面上のK7

[1]もし,K6が平面的であるならば,v=6,e=15.

  f=e−v=9

また,各面は少なくとも3つの辺をもたなければならないから,

  27=3f≦2e=30

となって矛盾は生じない.

[2]もし,K7が平面的であるならば,v=7,e=21.

  f=e−v=14

また,各面は少なくとも3つの辺をもたなければならないから,

  42=3f≦2e=42  (正則)

となって矛盾は生じない.

[3]もし,K8が平面的であるならば,v=8,e=28.

  f=e−v=20

また,各面は少なくとも3つの辺をもたなければならないから,

  60=3f≦2e=56

となって矛盾.

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

【2】球面上のK4

 もし,K4が平面的であるならば,v=4,e=6.

  f=2+e−v=4

また,各面は少なくとも3つの辺をもたなければならないから,

  12=3f≦2e=12  (正則)

となって矛盾は生じない.

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

【3】種数g表面上の正則平面グラフ

 Kvが平面的であるならば,q=v−1,e=v(v−1)/2.

  f=2−2g+e−v=2−2g+v(v−1)/2−v

また,各面は少なくとも3つの辺をもたなければならないから,

  3(2−2g+v(v−1)/2−v)=3f≦2e=v(v−1)

 正則正則平面グラフであるためには

  3(2−2g+v(v−1)/2−v)=v(v−1)

  g=(v−3)(v−4)/12

 この方程式には解が無数にあるが,

  g=0 → K4

  g=1 → K7

  g=6 → K12

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