第300回 グラフ理論:制約が生む世界(後編)

ついに連載300回です! 五色定理の証明に挑む「僕」たち。思わぬ情報で解決したかと思いきや……「グラフ理論」シーズンのクライマックスへ!

【お休みのお知らせ】

結城浩です。いつもご愛読ありがとうございます。 おかげさまでこのWeb連載も今回で第300回を迎えました!

みなさまの応援に感謝します!

さて、たいへん恐れ入りますが、さらなるパワーアップをはかるため、 このWeb連載の更新を2020年9月11日までお休みさせてください。

日程は以下の通りです。ご迷惑をおかけしますが、よろしくお願いいたします。

Web連載「数学ガールの秘密ノート」予定

・2020年8月7日(金)第300回更新
・2020年8月14日〜9月11日 お休み
・2020年9月18日(金)第301回更新
・(以後、毎週金曜日更新)

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

ミルカさん:数学が好きな高校生。 のクラスメート。長い黒髪の《饒舌才媛》。

$ \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\FOCUS}[1]{\fbox{$#1$}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\SET}[1]{\{\,#1\,\}} \newcommand{\EMPTYSET}{\{\,\}} $

高校の図書室にて

《カード》が一枚やってきた。

村木先生の《カード》

ミルカさん、テトラちゃん、そして僕の三人は、 そこに書かれていた《五色定理》の証明にチャレンジしていた(第299回参照)。

議論をしながら考えを進めていた途中、 机の《カード》を手に取ったミルカさんが、奇妙な声をあげた。

ミルカ「……ううっ!」

「ミルカさん、どうしたの?」

テトラ「ご気分でも悪いんですか?」

ミルカ「違う。《カード》の裏を見てしまっただけだ……」

「裏? その《カード》の裏に何か書いてあるの?」

村木先生の《カード》(裏面)

ミルカ「……」

「『すべての国が、六国以上に隣接する地図を描け。』」

テトラ「これは?」

「書いてある通りだね。どの国を選んでも、隣接国が六国以上ある……そんな地図を描いてみよ、という問題?」

ミルカ「ふむ……思いがけないところにspoilerがいたな」

ミルカさんは苦笑している。

テトラ「これがspoiler……ネタバレ? それは、どういうことでしょうか」

「隣接国の数というのは、双対グラフの言葉でいうと、まさに《次数》になるから、この問題はこう言い換えられるよね」

問題3(カードの裏)

すべての頂点の次数が6以上になる平面グラフを作れ。

※頂点の次数とは、その頂点から出ている辺の本数のこと。

ミルカ「グラフAにこだわりすぎたか(第299回参照)。spoilerを見てしまう前に、次数を増やしたグラフについて考えるべきだった。 しかし、まずは……」

「何はともあれ……」

テトラ「この平面グラフを作ってみるんですねっ!」

ミルカ「そうしよう」

「それに、カードの裏にあるこの問題は、《五色定理》のネタバレとは限らないよ。別の問題かもしれない」

テトラ「あっ、それに、もしかしたら、《五色定理》の方が裏かもしれませんし!」

ミルカ「村木先生の意図を探るよりも、グラフを描こう」

ミルカさんの言葉で、僕たちはいったん会話をストップ。

それぞれにグラフを描き始める。

議論するときは、みんなで議論する。

考えるときは、それぞれに考える。

グラフを描こう

グラフを描く。

平面グラフで、連結グラフで、そして……《どの頂点に注目しても、そこから出ている辺の本数が必ず6以上になっている》……そんなグラフだ。

もちろん、いま考えているグラフでは、ループはなく、多重辺もない。

さてさて……

テトラ「……これ、無理ですよね? 描いてみましたが……頂点七つのうち、次数が6になる頂点は二つしかできませんっ!」

テトラちゃんのグラフ

「無理だね。僕も似たようなグラフになった。正六角形を描いて、その中心から伸ばせば次数を6にすることはすぐできる。それから、まわりの頂点の一つを次数6にすることもできる。 でも、そのために辺をたくさん引くことになって、それが壁になってしまう……」

「僕」のグラフ

ミルカ「無理だな。私のグラフも同様だ」

ミルカさんのグラフ

「僕たちのグラフ、もしかしてすべて同型じゃない?」

テトラ「えっ」

ミルカ「そのようだな。次数と隣接点を考えれば、こんなふうに対応付けできる」

テトラ「やっぱり、村木先生のカードの裏の問題、つまり問題3は不可能……ですよね?」

「そうだね。次数を6以上にするためには、少なくとも頂点は七個以上必要。自分以外に六個の頂点がないと次数を6以上にできないから」

ミルカ「ふむ?」

「一方、僕たちが考えているグラフの頂点は七個。そしてこのグラフで不可能ならば、これ以上頂点を増やしても不可能」

テトラ「そうですね」

ミルカ「頂点を増やしても無駄だ、とすぐにはいえないな」

「だって、頂点を増やしても混雑するだけで、辺はかえって増やせなくなる」

ミルカ「それでは論証にならない。たとえば、私たちのグラフで次数が3の点のそばに新たな頂点を三個増やして辺で結べば、その頂点の次数は簡単に6に増やせる」

「いやいや、それはそうだけど、いま増やした新たな頂点に関しては次数1になってしまうよね。だから、やっぱりだめだよ。その新たな点も次数6以上にしなくちゃいけないんだから」

ミルカ「だからこそ論証が必要になるわけだ」

「確かにそうだけど……」

ミルカ「私たちは問題3の例を作ろうとして、不可能という予想を立てた。だから次に進む方向はもちろん……」

証明する方向だね」

テトラ「すべての頂点の次数が6以上になるような、そんな平面グラフは存在しない……ことを証明する?」

問題4

すべての頂点の次数が6以上になる平面グラフは存在しない。

それを証明せよ。

テトラ「……これは、見当も付きません。第一歩からわかりません。というか、第一歩は例を作ることで、それはもう済ませました。 そこから予想が出てきましたし、この主張の意味もよくわかっています。 でも……《証明としての第一歩》はどうしたらいいんでしょう」

証明としての第一歩はどうしよう?

「……」

テトラ「だって、平面グラフは無数に存在します。ちょっと辺を足したり、ちょっと頂点を付け加えれば、 ものすごく複雑なものまで作れますよね。無限に作れてしまいます。 もちろん《いかにも無理そう》というのはわかりますけれど」

ミルカ「無限には、論理で立ち向かう」

テトラ「論理……」

「僕たちが証明でよく使うのは二つだよね。《数学的帰納法》か《背理法》か。 すべての正の整数について何かを証明したかったら《数学的帰納法》が使えないかと考えるのは自然」

テトラ「《背理法》は……証明したいことの否定を仮定して、矛盾を導くんですよね」

「そうだね。《背理法》は難しいけれど、慣れれば考えやすくなる。たとえば、僕たちはいま、

 ○○○○が成り立つ平面グラフは存在しない

を証明したい。でも一つ一つ平面グラフを試して○○○○が成り立つかどうかを調べるのは大変」

テトラ「はい……はい、そうでした。《背理法》では、

 ○○○○が成り立つ平面グラフが存在する!

と仮定して話を進めていって、どこかで出てくるはずの矛盾を見つけるんですね」

「そうだね。それが考えやすいのは、《○○○○が成り立つ平面グラフ》を使って、議論を前へと進めることができるから」

テトラ「前へと進める……なるほど。今回の場合には、

 すべての頂点の次数が6以上になる平面グラフは存在する!

と仮定して話を進めることになります。 で、でも《すべての頂点の次数が6以上》ということから何が言えるのでしょう……」

「そうだなあ……」

そこで、ミルカさんが指を鳴らす。

ミルカ「すべての頂点の次数が6以上……ということは《次数の総和は、辺の数の二倍》が使えるな」

「確かに!」

テトラ「先ほどミルカさんがおっしゃっていた《自明な事実》ですね(第299回参照)」

ミルカ「そうだ。《次数の総和は、辺の数の二倍》とは、 あるグラフの次数の総和を$D$で表し、辺の本数を$E$とすると、 $$ D = 2E $$ がいえるということ」

「グラフのどの頂点についても次数は6以上だと仮定すると、$6V = D$になるよ。あ、違う、不等式だ。 $$ 6V \LEQ D $$ だね」

テトラ「あっ、急に見通しがよくなりました。$$ 6V \LEQ D = 2E $$ ということですよね。としたら、あたしたちのグラフではこんな不等式が成り立つことになりますね?」

$$ 3V \LEQ E \qquad \cdots\cdots\text{☆} $$

「そうだね」

テトラ「でも、あたしたちはここから矛盾を導かないといけないんですよね……この不等式はいったい何に矛盾するんでしょう」

ミルカ《条件をすべて使ったか》だな。私たちのグラフには強い制約があった。連結な平面グラフという制約だ。だから……」

「だから、うん、そうだね。わかったよ……」

テトラ「連結な平面グラフという制約から……矛盾を導く?」

「連結な平面グラフで成り立つ定理から出てくる、ある不等式と矛盾するんだよ」

テトラ「連結な平面グラフで成り立つ定理……ああ、オイラーの多面体定理!(第298回参照)」

オイラーの多面体定理

穴が空いていない多面体の頂点の数を$V$とし、辺の数を$E$とし、面の数を$F$とすると、 $$ V - E + F = 2 $$ が成り立つ。

※V, E, Fはそれぞれ頂点(vertex(複数形vertices))、辺(edge)、面(face)の頭文字。

連結な平面グラフで、頂点の数を$V$とし、辺の数を$E$とし、辺で囲まれた領域の数を$F$とすると、 $$ V - E + F = 2 $$ が成り立つ。

「そうだね。僕たちはそこから$F$を消した不等式を知ってる!」

テトラ「はいっ、知ってます! これです。$$ 6 \LEQ 3V - E \qquad \cdots\cdots\text{★} $$ ……ああ、でもこれは使えませんでしたよね。 これは、具体的な数を当てはめても成り立ってしまう不等式でしたから、矛盾は出ませんよね?」

「違う違う。それは二部グラフの判定のときのこと(第298回参照)。今度は違う。不等式$3V \LEQ E$と$6 \LEQ 3V - E$を使えば矛盾が出せるよ、テトラちゃん!」

テトラ「……そうですか? この二つから矛盾?」

$$ \begin{array}{rcllll} 3V &\LEQ& E &\qquad \cdots\cdots\text{☆} \\ 6 &\LEQ& 3V - E &\qquad \cdots\cdots\text{★} \end{array} $$

「そうだよ、だって(むぎゅ)」

ミルカさんの口を手でふさいだ。テトラちゃんに答えさせよという意味なんだろう。

……でも、ミルカさん! 口と鼻を同時にふさぐのはやめてくれ! テトラちゃん、早く早く!

テトラ「……わかりました! 確かに矛盾してます! ★の不等式、$$ 6 \LEQ 3V - E $$ から、いくつか移項すると、 $$ E \LEQ 3V - 6 $$ が言えますので、☆の$3V \LEQ E$を合わせると、 $$ 3V \LEQ E \LEQ 3V - 6 $$ となります。$3V \LEQ 3V - 6$なんてあり得ません。$0 \LEQ -6$ということですから。矛盾です!」

ミルカ「これで、連結な平面グラフでは「どの頂点についても、次数は6以上」は偽であることがいえた」

「(ぷはっ)ああ苦しかった。……そうだね」

ミルカ「これで、私たちはカード裏面の問いに答えることができたわけだ」

「すべての国が、六国以上に隣接する地図を描くのは不可能」

ネタバレ?

テトラ「ところで、実際のところ、すべての頂点の次数を6以上にするのは不可能だとして、これは《五色定理》の証明に関するネタバレになっているんでしょうか」

「すべての頂点の次数を6以上にすることはできないのはわかったけど、それがどんな手がかりになるかってことだね」

ミルカ「大きな手がかりだな。なぜかといえば、《すべて》を否定すると《存在する》が出てくるからだ。次の二つは同値」

  • 連結な平面グラフでは、すべての頂点の次数を6以上にすることはできない。
  • 連結な平面グラフには、次数が5以下の頂点が存在する。

テトラ「《次数が5以下の頂点》が存在する。《五色定理》の証明ではこれが鍵になる? ……かどうかは、まだわかりませんよね」

ミルカ「わからない。しかし、『連結な平面グラフの頂点が何個であったとしても《次数が5以下の頂点》が存在する』という主張は助かる。この頂点を使って考えを進めることができるからだ」

「確かに。その発想は背理法のときと一緒だね。《次数が5以下の頂点》に注目するわけだ!」

テトラ「ちょっと整理させてください。あたしたちは……」

  • あたしたちは《五色定理》を証明しようとしています。
  • 《五色定理》、つまり、連結な平面グラフは五彩色可能であるという定理です。
  • 言い換えると、任意の《連結な平面グラフ》の頂点彩色には五色あれば十分という定理です。

「そうだね」

テトラ「そして、あたしたちがいま手に入れた《武器》はこれですっ!」

  • 連結な平面グラフには、次数が5以下の頂点が存在する。

「……」

テトラ「……」

ミルカ「……」

「次の一歩は、数学的帰納法かな。頂点数に関する数学的帰納法だね、僕たちはすでにこれを証明している(第299回参照)」

  • 頂点数が5以下の連結な平面グラフはすべて五彩色可能である。

テトラ「そうですね」

「だから、あとはこれを証明すればいい」

  • 《頂点数が$n$以下の連結な平面グラフはすべて五彩色可能である》と仮定すると《頂点数が$n+1$の連結な平面グラフはすべて五彩色可能である》。
この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

トポロジーの世界に飛び込もう!

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに13巻以上も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

td2sk 5色定理か。ちょうど参考文献にも挙げられている『グラフ理論の魅惑の世界』で読んだところだ : 3ヶ月前 replyretweetfavorite

Led1192 完璧な伏線だった 3ヶ月前 replyretweetfavorite

aramisakihime まさかの伏線…とても面白かったです!(頂点1から3までのパスにある頂点の個数を、偶奇で場合分けしようとした泥沼の中から笑顔で) 3ヶ月前 replyretweetfavorite

Lsdu2DalePerry 「……これは、見当も付きません。第一歩からわかりません。・・・・・。 でも……《証明としての第一歩》はどうしたらいいんでしょう」 3ヶ月前 replyretweetfavorite