■平面グラフの頂点彩色(その9)
【補】四色問題
平面上の四色問題では,地図が平面ではなく球面上に描かれているものとすると,外部領域は他の領域と何の違いもないことになります.したがって,外部領域を塗っても塗らなくても構わないことになり,平面上の四色問題は球面上の四色問題と等価と考えることができます.
ヒーウッドは五色定理を鮮やかに証明できても,四色定理を証明することはできませんでした.したがって,平面・球面上の四色問題よりも先に,トーラス上の地図の塗り分けには7色必要であることが証明されたことになります.
ヒーウッドの式はgが正の数の場合にしか適用できないのですが,仮にg=0を代入するとH(0)=4となって,穴のあいていないトーラスすなわち球の表面に置かれた地図を塗り分けるために必要な色の数を正しく導き出すことができます.しかし,残念ながらこれは偶然の一致であり,ヒーウッド予想の証明から四色定理を導くことはできません.
トーラス面上の7色問題など大きい種数gに対するヒーウッドの公式は,平面上の四色問題が証明されるよりもかなり前に証明されているのですが,種数0の場合,つまり平面的集合の場合が最も難しいという事実は注目すべき事です.
四色問題の証明では,地図を電気回路とみなして
4f2+3f3+2f4+f5−f7−2f8−3f9−・・・=12
の条件の下の放電(電荷の移動)に帰着させる(放電法)のですが,この手続きにはどうしてもコンピュータが必要になりました.アペルとハーケンの後も放電法の改良が続けられ,1994年,ロバートソン,サンダース,シーモア,トーマスの4人が新たな1章をつけ加えました.
しかし,これとて基本的にはアペル,ハーケンと同じコンピュータ路線なのです.確かにコンピュータを使った証明を美しいあるいはエレガントな数学と呼ぶことはできないかもしれません.コンピュータを使わない証明にはこれまでにないようなまったく新しいアイディアが必要になると思われるのですが,そうしたアイディアは今日もなお登場していないのです.
===================================