第299回 シーズン30 エピソード9

グラフ理論：制約が生む世界（前編）

高校の図書室にて

テトラ「先輩、先輩！　《新作》来ましたよ！」

僕「ああ、テトラちゃん。《新作》？」

テトラ「村木先生からの《カード》ですよ！　カードといっても《封筒》ですけれど」

僕「また、村木先生の過剰な演出があるのかな？」

テトラ「今回の封筒は一つだけです。それに、 オセロの石も入ってないみたいですね（第294回参照）」

テトラ「先輩？」

僕「ん？」

テトラ「もしかして、いま『テトラは落ち着きが足りないぞ』とか思ってませんでした？」

僕「そんなこと、思ってないよ」

テトラ「そうですか……それで、 もしもお時間があったら、いっしょに考えませんか？」

僕「でもこれは《テトラちゃんへの問題》ということじゃないの？」

テトラ「村木先生によれば、みんなで楽しむように、だそうです」

僕「そうなんだ」

テトラ「あたし、先日の《オイラーの多面体定理》と《平面的グラフ》のお話（第298回参照）をレポートにして村木先生に持っていたんですよ。 そうしたら、この封筒をくださったんです」

僕「みんなで楽しむようにって？」

テトラ「はい。さっそく開けてみましょうっ！　いえ……開けてみることにいたしましょう……」

テトラ「はい、こちらが新作の《カード》でございます」

僕「これはこれはご丁寧に」

テトラ「（ふかぶか）」

僕「（ふかぶか）」

ミルカ「何をしてる？」

テトラ「きゃっ！」

僕「ミルカさん、いつ来たの？」

ミルカ「そんなことより、村木先生の《カード》を見よう」

村木先生の《カード》

僕「『どんな地図でも、五色で塗り分けられるか。』」

ミルカ「答えはイエス。しかし、村木先生のお題としては、《五色定理》の証明をせよということなんだろうな」

テトラ「五色定理の証明っ！？　そ、そんなことできるんですかっ？」

僕「テトラちゃん、どうしたの？」

テトラ「あたし……何かで読んだことがあります。 地図を塗り分ける問題のお話です。ものすごく難しい数学の問題で、 コンピュータを使って非常に多くの場合分けをしてようやく証明できた問題ですよね？　詳しくは知らないんですが、 コンピュータを使って数学の証明するなんてアリなんだって驚きました……」

僕「それは、五色定理じゃなくて《四色定理》だと思うよ、テトラちゃん」

テトラ「四色定理……五色じゃなくて四色？」

僕「うん、そうだよ。色を多く使える方が塗り分けするのは楽だよね。 だから、四色定理が超難問だとしても、 五色定理は、もしかしたら僕たちでも証明できるのかもしれない」

ミルカ「この《カード》は例によってアバウトな表現をしているから、私たちが考える問題を明確にしておこう」

僕「地図は有限個の国に分かれていて、 隣接している国は別の色で塗る必要がある。 点で接している国同士は隣接しているとは見なさない。 ああ、それから、一つの国が《飛び地》になっていることはないというのも？」

ミルカ「ふむ。それから、地図は平面上にある、というのも」

テトラ「それはそうですよね」

ミルカ「平面上に限るのは、たとえば、トーラス上の地図は除外して考えるという意味。 トーラス上の地図は、確か塗り分けに七色必要だったはずだ」

テトラ「トーラスというのはドーナッツの表面ですね」

ミルカ「そう」

テトラ「それにしても、四色定理ほどではないとしても、五色定理は証明できるんでしょうか」

ミルカ「ともかく、地図の双対グラフに対して頂点彩色をしていこう。 地図であるという制約は、双対グラフが平面グラフであるという制約になる」

テトラ「双対グラフ？」

僕「二色塗り分けのときに使ったグラフじゃないかな（第293回参照）。 国を頂点と見なし、国境を辺とみなしたグラフのことだよね？」

ミルカ「そう」

テトラ「あら？　ちょっとお待ちください。だとしたらすでに二色で塗り分けできることは証明しませんでしたっけ？」

僕「それは、国境がすべて地図の端まで直線で伸びていた場合だよね。 直線で世界が二分されて、片側の色をすべて反転する技法が使えたんだから」

テトラ「ああ、そうでした、そうでした。いわば《色反転の技法》ですね（第293回参照）」

僕「《三国地図》を考えれば、二色では色が足りないのはすぐわかるね」

テトラ「国が三つ……二色で足りなくなるのは頂点が三個のグラフだからですね」

ミルカ「頂点が三個でも、二彩色可能なグラフはある」

テトラ「あ、ええと……」

僕「テトラちゃんが言いたかったのは、

　《頂点三個のグラフの中には、二彩色不可能なグラフが存在する》

ということだね。そしてミルカさんが言ったのは、

　《すべての頂点三個のグラフは、二彩色不可能である》は偽である

ということで、どちらも正しいんじゃないの？」

テトラ「……」

僕「だよね、テトラちゃん？」

テトラ「は、はい、そうです。あの……いまさらですけれど、 論理って大切なんですね。論理を意識しないと、言いたいことがうまく伝わりません」

ミルカ「特に、量化子（りょうかし）だな。 $\exists$ と $\forall$」

僕「$\exists x\, P(x)$ の方は、 $P(x)$ を満たす $x$ が存在するということだね。 $P(x)$ を満たす $x$ が、 たった一つでも存在するとき、 $\exists x\, P(x)$ は真になる」

テトラ「はい……」

僕「それから、 $\forall x\, P(x)$ の方は、 どんな $x$ を持ってきても $P(x)$ を満たすとき、 $\forall x\, P(x)$ は真になる」

テトラ「量化子……意識するように注意します」

ミルカ「結局、こんな問題として考えよう」

僕「ミルカさんは、五色定理の証明を知っているの？」

ミルカ「いや知らない。だからspoilerの心配なく、安心して話せる」

テトラ「ネタバレなしですねっ！　……あっ、でも、テトラを置いてけぼりにしないでください。あたしもきちんと考えたいですから」