■平面グラフの頂点彩色(その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
===================================