■平面グラフの頂点彩色(その30)
【10】種数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
===================================