■ヒーウッドの七色定理(その5)

グラフの種数とは、グラフを辺が交差しないように描画できるようにするために、球面に追加しなければならない取っ手の最小数である。

リンゲルとヤングスが解決した問題は、向き付け可能なグラフの種数と関係している。

たとえば、K5はトーラス面上には描画可能であるが、球面上には描画不可能である(種数1)。

Knの種数がgnならば、n色が必要となるgn個の取っ手をもつ曲面上の地図が存在するということである。

gn=(n-3)(n-4)/12のceiling

であることから、g>1に対して

  H(g)=[{7+√(1+48g)}/2]

が導かれる。

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

【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

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