研究紹介 (鈴木 有祐)
研究テーマ: 位相幾何学的グラフ理論

1

四色問題

みなさんは有名な四色問題を知っていますか？私の研究する位相幾何学的グラ
フ理論において，最も有名な問題（定理）と言っても良いものだと思います．内容は以下のようなものです．
問題１: 平面上の地図は何色あれば塗り分け可能か？（隣り合う国を別の色で塗るというルールで．
）この問題の意味は誰でもわかるでしょう．それこそ，白地図と色鉛筆さえあれば幼稚園に通う子供でも試行錯誤しながら手を動かし，問題を考えることができるはずです（図 1，2 参照）．それを行っていくうちに，4 色あればどんな地図でも塗り分けられることが分かってきます．では，本当に 4 色あれば十分なのでしょうか？言い換えれば，5 色の色鉛筆が必要になってしまう地図ってあるのでしょうか？当然ですが，「経験上，4 色のものしかないから，4 色で十分だろう．
」という発想ではいけません．やはり，しっかりとした結論と，その理由が知りたくなるものですよね．実際，上の問題１の解答として以下の定理が与えられています：
定理１: 平面上の地図は 4 色あれば塗り分け可能である．

図 1: Honsyu 王国地図

図 2: Honsyu 王国 4 色塗り分け

1ああ，やっぱり予想通りだったか．大方のみなさんはそう思われたことでしょう．しかし，そう簡単に納得されては困りますよ．なにしろ，問題１が提起されてから，上の定理が得られるまで実に 100 年以上の年月がかかっているのですから！
（問題１は 1852 年に提起され，1976 年，K.Appel と W.Haken によって解決．
これらの歴史に関しては多くの文献に記述されています．例えば [2, 3] 参照.）問題の内容は誰でもわかるのに，それの問題を誰も解けない・・・，その事実だけでも多くの人の好奇心を魅了しますよね．
（まさに，“良い問題” と言ってよいでしょう．
）

図 3: Honsyu 王国双対グラフ

図 4: Honsyu 王国双対グラフの頂点彩色

この問題は，（上図の Honsyu 王国において）対応する県に点（頂点）を配置し，隣接する県どうしを線（辺）で結んでできた（離散）グラフという図形の問題と考えることができます（図 3 参照）．それらのグラフの頂点が何色で塗り分けられるのか？
（もちろん，隣接する頂点同士は異なる色で塗る．
）図 2 と図 4 を対応させれば，それらの問題が同じものであることを理解するのは難しくないでしょう．

2

位相幾何学的グラフ理論とは？

グラフ理論とは組合せ論の中の中心的な一分野で，近年のコンピュータ，ネットワーク等の発達とともに成長してきた数学です．扱うのは第 1 章で紹介した，“頂点” と “辺” からなる “グラフ” と呼ばれる図形です．実際はもう少し抽象的に，「集(V )合 V とその 2 元部分集合 E ⊆ 2 の組 (V, E)」と定義されます．このようにして定義されたグラフの構造を明らかにしていく, 大雑把に言うとこれがグラフ理論の研究です．さらに，球面（平面）や浮き輪の表面（トーラス）のような舞台（閉曲面と呼ばれる）に辺の公差なく描画された（埋め込まれた）グラフを研究対象とするのが位相幾何学的グラフ理論です．前述の四色問題が，この位相幾何学的グラフ理論のお話であることがお分かりいただけたと思います．ちなみに，トーラ
ス上では 4 色で塗り分けられないグラフが存在し，実は 7 色必要（かつ十分）だということが知られています．
位相幾何学的グラフ理論には，我々がこれまで受験勉強等で学習してきた微分積分の数式等がほとんど登場しません．サインやコサインなども出てきません．
（グ2ラフに対する何かの不変量を評価する場合には，多少計算をしなければならない場合もありますが．
）では，どのように，証明を行うのか？これまで学んだ数学の基礎知識が余り活躍しない分，逆に丸腰の状態で議論を進めなければいけないことになるでしょう．これが，この分野の面白い部分であり，また難しいところでもあります．問題が理解しやすいだけに，「あ，これはパズルみたいで簡単そうだな．
」等と思うと足元をすくわれてしまうかもしれませんよ．

3

五色定理の証明

この章では，位相幾何学的グラフ理論における論証の雰囲気をつかんでもらうために，五色定理の証明をお見せしたいと思います．
「あれ，四色定理ではなかったのかな？」と思った人もいると思いますが，間違いではありません．実際，多くの数学者の 100 年以上にわたるチャレンジを退けてきた四色問題を，この場で解説するにはあまりにもページ数が足りません．そこで，「五色定理」というわけです．皆さんお察しの通り，五色定理は四色定理を証明するのより簡単です．また，四色定理を仮定してしまえば，自明な（あたりまえな）事実です．
（なぜ？理由を考えてみよう．高校で学習した「必要条件」や「十分条件」はしっかりわかっているかな？ただ矢印の方向を暗記しているだけでは真の理解には程遠いかも・・・．
）
そのまえに，ちょっとだけグラフ理論の用語を紹介したいと思います．あるグラ
フ G において指定された頂点 v に接続する辺の本数を，その頂点 v の次数と呼びます．例えば図 3 においては，Niigata 県に対応する頂点の次数は 5 ということになりますね．
（あくまで Honsyu 王国です．
）また，ここでは事実を書き記すだけにとどめておきますが，平面グラフ（平面上に埋め込まれたグラフ）は必ず次数 5 以下の頂点を含むことも知られています．
定理２: 平面上の地図は 5 色あれば塗り分け可能である．
（証明）平面グラフの頂点彩色（隣接する頂点を異なる色で塗る）を考えます．こ
こではグラフの頂点数に関する数学的帰納法を用います．頂点数が十分小さいグ
ラフが 5 色で彩色可能なことは簡単に確認できますので（実際には 4 色で塗れますが），帰納法の第一段階は大丈夫です．
そこで，頂点数 n の平面グラフ G を考えます．上述の事実より，この G は次数が 5 以下の頂点を含みます．まず手始めに，G が次数 4 の頂点 v を含むと仮定しましょう．このとき G から，頂点 v と v に接続する 4 本の辺を取り除いたグラフ
G′ = G − v を考えます（G′ の頂点数は明らかに n − 1）．数学的帰納法の仮定より，G′ は 5-彩色可能です．
（わかるかな？）このとき，もともとの v の隣接頂点をv1 , v2 , v3 , v4 とすれば，それらは高々4 色の色で塗られています．その 4 色に含まれない 5 色目の色を（G において）v に塗ってあげれば，G の 5-彩色が得られます．
同様の議論で，G が次数 3 以下の頂点を含む場合も証明可能です．

3

図 6: (赤, 黄)-鎖２

図 5: (赤, 黄)-鎖１

今，G は次数 4 以下の頂点を含まないとしてよいでしょう．このとき上述の事実から，G は必ず次数 5 の頂点を含みます．
（その頂点を v とし，v の隣接頂点を時計回りに v1 , v2 , v3 , v4 , v5 とします．
）上の議論と同様 G′ = G − v を考えたとき，G′ は5-彩色可能なわけですが，その 5-彩色において v1 , v2 , v3 , v4 , v5 を塗る色が高々4 色であれば，上と全く同じ議論が動いてしまいます．そこで，v1 , v2 , v3 , v4 , v5 にはそれそれ順番に赤，青，黄，緑，紫の色がそれぞれ塗られているものとしましょう．
ここで，v1 から辺をたどっていけるひと固まりのグラフで（部分グラフという）赤頂点と黄頂点のみからなるものを (赤, 黄)-鎖とよぶことにしましょう（図 5 参照）．
もしこの (赤, 黄)-鎖が頂点 v3 を含んでいなければ（v3 に届いていなければ），図6 のように (赤, 黄)-鎖中の赤と黄色をそっくり塗り替えてしまいます．すると，頂点 v が赤で塗れることになりもとの G が 5-彩色可能であることが示せます．
(赤, 黄)-鎖が頂点 v3 を含んでしまうと（図 7），残念ながら上と同じ論法は使えません．そこで，今度は図 8 のように，頂点 v2 から始まる (青, 緑)-鎖を考えます．
図を見れば一目瞭然ですが，この (青, 緑)-鎖が頂点 v4 に届くことはありません．したがって，青と緑を交換することができ，v を緑で塗ることが可能になります．これでどのように考えていっても G の 5-彩色が構成できることがわかりました．
（将棋で言うとようやく「詰んだ！」というイメージでしょうか．
）

図 7: (赤, 黄)-鎖３

図 8: (赤, 黄)-鎖と (青, 緑)-鎖4どうだったでしょうか．すんなり議論についてくることができましたか？論文や教科書で，ここまで丁寧に証明を書いているものはあまりないはずです．
（ある程度分かっている者同士は無駄に長い文章や図を省くため．
）そのため通常証明の内容を追う際には，教科書の欄外や論文の余白に沢山の図を自力で描いて自分なりの理解をしていこうという姿勢が重要になってきます．

4さらなる深淵へ (Hadwiger 予想)

前章では，位相幾何学的グラフ理論における論証の雰囲気をつかんでもらうた
め，簡単な五色定理の証明を追いかけてもらいました．前述のように，実際は四色定理が示されているわけですが，その証明は膨大である上，計算機を用いたものであったため，当初はそれが数学の証明であるのか否か物議をかもしたようです．現在はプログラムや証明そのものの改良がなされているようですが，この場でその詳細を記述することは不可能でしょう．ここで断っておきますが，四色定理が解けたことによってグラフ理論の全てが分かったわけではありません．四色定理の一般化として，以下の Hadweiger 予想というものがあります．
予想 (Hadwiger): グラフ G が n 点からなる完全グラフ Kn をマイナーとして含まなければ，G は (n − 1)-彩色可能である．
用語もしっかり定義しないまま予想を紹介してしまいましたが，本稿の趣旨と反するのであえて深入りすることは避けましょう．(この予想自体は一般の抽象グラフに対するもので，閉曲面上に埋め込まれたグラフに限定されたものではありません．) 何が言いたかったかというと，数学にはまだまだ多くの未解決問題があるということです．上の予想の n ≤ 2 の場合は自明であり，n = 3, 4 の場合も少々考えればわかる問題です．n = 5, 6 の場合は，実は本稿でお話しした四色定理と同値であることが知られています．
（すなわち，四色定理が証明できれば Hadwiger 予想の n = 5, 6 の場合も証明できるし，その逆もまたしかり，ということです．
）n ≥ 7の場合は予想は未解決のままで，現在も多くの研究者がその解決に向けて研究を継続中です．
（私も閉曲面上のグラフに限定し，[5] の部分的解決を得ております．
）
私の研究分野である位相幾何学的グラフ理論には上記以外にも山のような未解決問題があり，現在も国内外の研究者と協力しながらそれらの解決に向けて研究を進めております．短い文章になってしまいましたが，位相幾何学的グラフ理論の魅力を少しでも感じてもらえたなら幸いです．主に高校生向けにということで“わかりやすさ” を最優先としたため，定義があいまいな部分や説明のくどい部分があることはご了承ください．

参考文献[1] 根上生也: 位相幾何学的グラフ理論入門, 横浜図書, 2001.
5

[2] 一松信: 四色問題, 講談社ブルーバックス, 1978.
[3] 前原潤，根上生也: 幾何学的グラフ理論, 朝倉書店, 1992.
[4] R.Diestel: Graph Theory, Springer, 1997.
[5] R. Mukae, A. Nakamoto, Y. Oda, Y. Suzuki, K6 -Minors in triangulations on
the nonorientable surface of genus 3, Graphs Combin., 26 (2010), 559–570.

6