第298回 シーズン30 エピソード8

グラフ理論：壁の中、壁の外（後編）

僕「……ごめんごめん。 僕はぜんぜん《パズル》とは別のことを考えていたんだ。 立方体を押しつぶす話。ミルカさんから聞いたんだけど」

テトラ「立方体を押しつぶす……って、どんなお話でしょう」

僕「立方体をべちゃっと平面上に押しつぶす。こんなふうにね」

テトラ「これは、左の立方体を上から押しつぶしたようすですか？」

僕「そうそう。そんなふうに押しつぶしても、頂点の数や辺の数は変わらない。 それから、つながり方も変わらない。 立方体の底面、この図だと６番の面は、押しつぶしたらなくなっちゃうみたいだけど、 外側全体の領域を一つの面と考えるなら、 つじつまがあっているといえる」

テトラ「つじつまがあっている……？」

僕「ああ、うん、どの面とどの面が接しているか、その境界にあたる辺はどれか……という《つながり方》は押しつぶしても変わらないよね。 たとえば、６番の面は、２，３，４，５番の面と接している。 トポロジーの話題になったとき、ミルカさんは、 そんなふうに《つながり方》を変えずに立方体を押しつぶす話をしてくれたことがあったんだ（『数学ガール／ポアンカレ予想』参照） ……あれ、ちょっと待って？」

テトラ「？」

僕「ちょっと待って。それを使えないかな？」

テトラ「それ……？」

僕「立方体をつぶして平面にしちゃうんだよ！　立方体は連結グラフだと思うことができる。 頂点があって、二つの頂点のあいだに辺がある。ループはないし、多重辺もない。 立方体は平面につぶせるから、平面的グラフといえる。辺が交差しないように立方体をつぶせるからね」

テトラ「立方体の頂点は八個で、辺は十二本あります。 小さな例から少しずつ考えてきましたが、急に大きな例にしちゃうんですか……？」

僕「うん、ちょっと例の大きさはさておく。 思いついたのは、 立体となったグラフを平面につぶすというアイディアなんだ。 例を作っているときには、辺で囲まれたところを《領域》と呼んでいたから気付かなかった。 《面》と呼べば気付いたかもしれない！」

テトラ「ええっと……何に気付いたんでしょう？」

僕「オイラーの多面体定理だよ！」

テトラ「オイラーの多面体定理……え、ちょっと意味がわかりません。 $V - E + F = 2$ という等式が成り立つということですか」

僕「そうだよ。割と有名な等式だね。 個数の関係を表しているだけだから、主張自体はそんなに難しくないと思うけど」

テトラ「あ、いえ、意味はわかります。 あたしが言いたかったのは『こんな等式がほんとうに成り立つの？』ということです」

僕「驚きだよね」

テトラ「た、試してみます。立方体の頂点は $8$ 個で、辺は $12$ 本で、面は $6$ 個ですね。

つまり、 $$ V = 8, \quad E = 12, \quad F = 6 $$ です。 $V - E + F$ を計算すると…… $$ V - E + F = 8 - 12 + 6 = 2 $$ ……ほんとですね！！」

僕「立方体に限らないし、正多面体とも限らないよ。たとえば四角錐を考えると、

頂点は $5$ 個、辺は $8$ 本、面は $5$ 個だから、 $$ V = 5, \quad E = 8, \quad F = 5 $$ になる。 $V - E + F$ を計算すると…… $$ V - E + F = 5 - 8 + 5 = 2 $$ ……になるね」

テトラ「あららら……」

僕「たとえば、こんな適当な多面体でもいいよ」

テトラ「数えてみます…… $$ V = 7,\quad E = 12,\quad F = 7 $$ ……ですね。 $$ V - E + F = 7 - 12 + 7 = 2 $$ はい、確かに成り立ちます。 これは、驚きですっ！　……驚きなんですが、 これが《パズルのグラフ》と関係があるんでしょうか？」

僕「そうそう、そうだった。 あのね、さっきは立方体を押しつぶしたけど、 その逆をやってもいいよね。辺が交差しない、平面に描かれたグラフがあったとする。 そのグラフを立体に持ち上げて、外周に面を張る」

テトラ「……」

僕「そのような操作をしても、頂点の数・辺の数・面の数には変わりはないし、 つながり方も変わらない」

テトラ「あっ、わかりました。ということはオイラーの多面体定理が成り立つ？」

僕「その通り！　僕たちはいま《パズルのグラフ》が平面に描けるかどうかを考えていた」

テトラ「はい。平面的グラフになるかどうか……」

僕「話を簡単にするために、連結グラフに限定して考えていた。 つまり最初からばらばらになったグラフは除外して考えていたから、 オイラーの多面体定理を使うと、こんなことがいえる」

テトラ「あっあっ！　これで判定ができるんですね」

僕「うん、そうだね。 《平面的グラフならば、 $V - E + F = 2$》はいえる。 あ、ちょっと待って……うん、大丈夫」

テトラ「？」

僕「平面的グラフで、 面を作らない辺が枝のように伸びていたとしても大丈夫かなと思ったんだけど、 大丈夫だった。面を作らない辺が枝のように伸びているときは、 $V$ と $E$ は同数で増えるから、影響はない。 だから《平面的グラフならば、 $V - E + F = 2$》はいえる。 逆の《$V - E + F = 2$ ならば、平面的グラフ》かどうかはわからないけれどね」

テトラ「あれ……でも、あたしたちが知りたいのは《パズルのグラフ》が平面的グラフかどうかですから、 《平面的グラフならば……》という定理があっても使えないんじゃありませんか？」

僕「そうじゃないんだよ。 $\heartsuit$ の対偶を考えればすぐにわかる」

テトラ「なるほど……平面的グラフではないという判定に使えるんですね？」

僕「そうそう。 命題とその対偶の真偽は必ず一致するからね」

テトラ「ということは《パズルのグラフ》で、 $V - E + F$ を《計算》して、 $2$ にならないなら、 つまり、 $$ V - E + F \NEQ 2 $$ がいえれば証明完了ですねっ！　 $V - E + F$ って、何て素敵な式でしょう！」

僕「さっそく計算してみよう！」

テトラ「先輩……」

僕「困った……」

テトラ「《パズルのグラフ》では、頂点の数は $V = 6$ で、 辺の数は $E = 9$ ですが……」

僕「面の数がわからないね……」

テトラ「はい。そもそも平面に描けないんですから……面？」