今回のコラムのテーマは，種数ｇの閉曲面上の地図の彩色数に関するヒーウッドの公式（必要条件）の導出です．

　以下，

　　Ｈ（ｇ）＝［｛７＋√（１＋４８ｇ）｝／２］

と同値な

　　Ｈ（χ）＝［｛７＋√（４９−２４χ）｝／２］

について，一松信先生よりご教示された証明を紹介いたします．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】目標

　面上の多角形分割で，面数Ｆ，頂点数Ｖ，辺数Ｅとするとき，オイラー標数

　　χ＝Ｆ＋Ｖ−Ｅ･･･････(1)

の閉曲面（向きづけられるか否かは不問）上の地図は，辺で境される国を別の色で塗るという条件下において，ヒーウッドの数

　　Ｈ（χ）＝［｛７＋√（４９−２４χ）｝／２］　　（［・］は切り捨て）

色あれば塗り分けられる（十分条件）．

［注１］この公式は本来χ＜０の場合にのみ有効である．ただし結果的にχ＝１（射影平面）とχ＝０で向きづけられる曲面（輪環面）では必要十分な正しい値（それぞれ６と７）を与える．χ＝２（球面）のときには４を与えるが，これは「偶然の一致」であって四色問題の解ではない（∵上の公式を導くときχ＜０という条件を本質的に使っている）．

［注２］これは十分条件であって，必要条件（どうしてもそれだけの色がいる）ではない．結果的にはχ＝０で向きづけられない曲面（クラインの瓶）以外の曲面ではすべて正しく必要十分な色数を与えている．クラインの瓶は唯一の例外で公式の値は７だが，実は６色で必要十分である．必要性は部分的（χの特別な値の例）には１９世紀末から知られていたが，最終的にはヤングスとリンゲルとが共同研究して１９６８年に完全に証明された．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】証明

［１］第１段階

　まず，地図を次のような標準地図に限定しても一般性を失わない．すべての頂点にはちょうど３個国が会している（４個以上が１点に会することはない）．−−−それには４個以上が１点に会していたら，その点の近くに新しい１国を作って地図を修正すればよい（必要なら後にその国をつぶしてもとに戻す）．

　したがって，面（国）の数をＦ，頂点数をＶ，辺数をＥとするとき

　　３Ｖ＝２Ｅ･･･････(2)

としてよい．

［注］χ＝Ｆ＋Ｖ−Ｅ･･･････(1)

オイラー標数の定義．この基本量の値は曲面を定めれば一定であることは曲面（２次元多様体）のトポロジーの基本定理で，これは既知とする．向きづけられる場合はχ＝２−２ｇ（ｇはgenus（示性数，種数））であり，彩色数などと関連するのはある意味では自然な話である．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［２］第２段階

　Ｎ色で十分であることは，Ｆ＞Ｎのとき必ずＮ−１辺以下の国があることを示せばよい．（Ｆ≦ＮならＮ色で塗り分けられるのが自明である．）Ｎ−１辺以下の国があれば，一時，その国を隣接する国の１つと合併させる．そうすると辺の数が１つ減るから，Ｆに関する数学的帰納法によってＦ−１国以下の地図でよいと仮定して（Ｎ国以下なら自明）とりあえず塗り分ける．その後，もとの国を独立させたとき周りにＮ−１国以下しかないから，Ｎ−１色で十分なので，残った色をその国に与えればＦ国のときも正しい・・・という形で数学的帰納法による証明ができる

［注］互いに接するＮ国があるか否かは必要性の証明には不可欠だが，十分性の証明には不必要である．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［３］第３段階

　少しわかりにくい条件だが次の補助定理を証明する．

　　「オイラー標数の閉曲面上の標準地図に対して，ある正の整数Ｎがあり，Ｆ＞Ｎである任意の整数Ｆについて，不等式

　　ＮＦ＞６（Ｆ−χ）･･･････(3)

が成立する．」

という条件があれば，Ｆ（＞Ｎ）国からなる標準地図中に必ずＮ−１辺以下の国がある．

証）結果を否定すると，すべての国がＮ辺以上だから，のべＮＦ本以上の辺が２回数えられるので

　　ＮＦ≦２Ｅ･･･････(4)

である．(2)を(1)に代入すると

　　χ＝Ｆ＋Ｖ−Ｅ＝Ｆ＋２／３Ｅ−Ｅ＝Ｆ−１／３Ｅ

であり，

　　Ｆ−χ＝Ｅ／３≧ＮＦ／６

すなわち，６（Ｆ−χ）≧ＮＦを得る．これは条件(3)の不等式と矛盾する．

系）したがって，その標準地図ではＮ色で塗り分けられる（第２段階の帰納法）．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［４］第４段階

　条件(3)を満たす最小のＮ0を求める．χの正負によって場合分けがいる．

(i)χ＞０のとき，Ｎ0＝６とすれば明らかである．

［注］χ＝１のときには実際に６色が必要十分である．χ＝０のときには６−１＝５辺以下の国があるという事実は正しく，６色で十分なことが導かれる．ただしこれは不完全な結果である．ケンペの方法によって５色で十分なことが証明できる．４色で十分という四色問題はこれとは別の大問題（大定理）である．

(ii)χ＝０のときＮ0＝７が最低である．実際向きづけられるときには７色が必要十分である．

(iii)χ＜０のとき（このときが本題），Ｎ≧７でなければならない．(3)を（Ｎ−６）Ｆ＞−６χ＞０と置き換える．Ｎ−６＞だからＦが大きいほど有利である．したがって，Ｆ＞Ｎである最低のＦ＝Ｎ＋１について成立すればよい．

　　（Ｎ−６）（Ｎ＋１）＋６χ＞０

とすると，Ｎに関する２次不等式

　　Ｎ^2−５Ｎ＋（６χ−６）＞０

を与える．Ｎ＞０だから，この解は

　　Ｎ＞｛（５＋√（２５−４（６χ−６））／２｝＝｛（５＋√（４９−２４））／２｝

を得る．

　Ｎは整数である（本当に大きい）から，最低の値は

　　Ｎ0＝［右辺＋１］＝［｛７＋√（４９−２４χ）｝／２］

［注］具体的な数値を示すと次の通りになる．

　　ｇ（向きづけられるときのｇ）

　　Ｎ0（ヒーウッドの数）：［４］は機械的な計算（前述の注参照）

χ ：　２　　１　　０　−１　−２　−３　−４　−５　−６　−７　−８　−９　−１０

ｇ ：　２　　　　　１　　　　　２　　　　　３　　　　　４　　　　　５　　　　　　６

Ｎ0：［４］　６　　７　　７　　８　　９　　９　１０　１０　１０　１１　１１　　１２

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝