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

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