連結グラフは，いくつかの頂点とそれに連結するすべての辺を除けば分割することができる．ｈ個の頂点の除去で分割されるならば，それはｈ連結であるという．

　連結数をｈとした場合の彩色数は

　　Ｈ（ｈ）＝［｛７＋√（２４ｈ−２３）｝／２］

で与えられる．

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

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

であるから，

　　ｈ＝２ｇ＋１

　　ｈ＝−χ＋３

と同値である．

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

【１】目標

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

　　３−ｈ＝Ｆ＋Ｖ−Ｅ･･･････(1)

　　Ｆ＋ｈ−３＝Ｅ−ｖ

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

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

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

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

【２】証明

［１］第１段階

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

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

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

としてよい．

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

［２］第２段階

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

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

［３］第３段階

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

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

　　ＮＦ＞６（Ｆ＋ｈ−３）･･･････(3)

が成立する．」

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

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

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

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

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

であり，

　　Ｆ＋ｈ−３＝Ｅ／３≧ＮＦ／６

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

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

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

［４］第４段階

　条件(3)

　　Ｎ＞６（１＋（ｈ−３）／Ｆ）･･･････(3)

を満たす最小のＮ0を求める．ＦにはＮより大きいすべての整数をだいにゅうするものとする．χの正負によって場合分けがいる．

(i)ｈ＝１，２のとき，Ｎ0＝６とすれば明らかである．

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

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

　　（Ｎ−６）（Ｎ＋１）＋６（３−ｈ）＞０

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

　　Ｎ^2−５Ｎ＋（１２−６ｈ）＞０

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

　　Ｎ＞｛（５＋√（２５−４（１２−６ｈ））／２｝＝｛（５＋√（２４ｈ−２３））／２｝

を得る．

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

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

　　ｈ：１，２，３，４，５，６，７，　８，　９，１０，１１，１２，１３

　　Ｈ：４，６，７，７，８，９，９，１０，１０，１０，１１，１１，１２

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