■平面グラフの頂点彩色(その19)
【2】g個の穴があいたトーラス面上の地図の塗り分け
これを証明したヒーウッドは,さらにg個の穴があいたトーラス上の地図に関するオイラーの公式
v−e+f=2−2g
を利用して
(1)2個の穴があいているトーラス上の地図はどれも8色で塗り分けられる
(2)3個の穴があいているトーラス上の地図はどれも9色で塗り分けられる
・・・・・・・・・・・・・・・・・・・・・・・・
(3)10個の穴があいているトーラス上の地図はどれも14色で塗り分けられる
に引き続いて,
(4)g個の穴があいているトーラス上の地図はどれもH(g)色で塗り分けられる
H(g)=[{7+√(1+48g)}/2]
を証明した.
[・]はガウス記号で,
g:1,2,3, 4, 5, 6, 7, 8, 9,10
H:7,8,9,10,11,12,12,13,13,14
となるのであるが,ヒーウッドはg≧2に対してそのような地図が実在することを示すことはできなかったため,この問題は「ヒーウッド予想」と呼ばれることになった.
1968年,リンゲルとヤングスは,g個の穴のあいているトーラス上にこれだけの色を必要とする地図が存在することを証明した.ヒーウッド予想(1890年)が最終的に証明されるまでには77年もの歳月が必要だったというわけである.
ヒーウッドの式はgが正の数の場合にしか適用できないのであるが,仮にg=0を代入するとH(0)=4となって,穴のあいていないトーラスすなわち球の表面に置かれた地図を塗り分けるために必要な色の数を正しく導き出すことができる.しかし,残念ながらこれは偶然の一致であり,ヒーウッド予想の証明から四色定理を導くことはできない.結局,ヒーウッドは五色定理を鮮やかに証明できても,四色定理を証明することはできなかった.したがって,平面・球面上の四色問題よりも先に,トーラス上の地図の塗り分けには7色必要であることが証明されたことになる.
===================================