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

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

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

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

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

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

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

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

が導かれる。

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