■ハンドルの球面埋め込み(その7)

【2】証明

[1]第1段階

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

 したがって,面(国)の数をF,頂点数をV,辺数をEとするとき

  3V=2E・・・・・・・(2)

としてよい.

[注]χ=F+V−E・・・・・・・(1)

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

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

[2]第2段階

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

[注]互いに接するN国があるか否かは必要性の証明には不可欠だが,十分性の証明には不必要である.

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

[3]第3段階

 少しわかりにくい条件だが次の補助定理を証明する.</P>

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

  NF>6(F−χ)・・・・・・・(3)

が成立する.」

という条件があれば,F(>N)国からなる標準地図中に必ずN−1辺以下の国がある.

証)結果を否定すると,すべての国がN辺以上だから,のべNF本以上の辺が2回数えられるので

  NF≦2E・・・・・・・(4)

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

  χ=F+V−E=F+2/3E−E=F−1/3E

であり,

  F−χ=E/3≧NF/6

すなわち,6(F−χ)≧NFを得る.これは条件(3)の不等式と矛盾する.

系)したがって,その標準地図ではN色で塗り分けられる(第2段階の帰納法).

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

[4]第4段階

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

(i)χ>0のとき,N0=6とすれば明らかである.

[注]χ=1のときには実際に6色が必要十分である.χ=0のときには6−1=5辺以下の国があるという事実は正しく,6色で十分なことが導かれる.ただしこれは不完全な結果である.ケンペの方法によって5色で十分なことが証明できる.4色で十分という四色問題はこれとは別の大問題(大定理)である.

(ii)χ=0のときN0=7が最低である.実際向きづけられるときには7色が必要十分である.

(iii)χ<0のとき(このときが本題),N≧7でなければならない.(3)を(N−6)F>−6χ>0と置き換える.N−6>だからFが大きいほど有利である.したがって,F>Nである最低のF=N+1について成立すればよい.

  (N−6)(N+1)+6χ>0

とすると,Nに関する2次不等式

  N^2−5N+(6χ−6)>0

を与える.N>0だから,この解は

  N>{(5+√(25−4(6χ−6))/2}={(5+√(49−24χ))/2}

を得る.

 Nは整数である(本当に大きい)から,最低の値は

  N0=[右辺+1]=[{7+√(49−24χ)}/2]

[注]具体的な数値を示すと次の通りになる.

  g(向きづけられるときのg)

  N0(ヒーウッドの数):[4]は機械的な計算(前述の注参照)

χ : 2  1  0 −1 −2 −3 −4 −5 −6 −7 −8 −9 −10

g : 2     1     2     3     4     5      6

N0:[4] 6  7  7  8  9  9 10 10 10 11 11  12

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