拠点巡り（問題）

先月号では，無限モグラ国を走る地下トンネル通路網の話にお付き合いいただいたが，今月号はその続きの話を楽しんでいただきたい。

　トンネル通路はあちこちで枝分かれしていて，3次元空間を縦横に駆使してありとあらゆる方向に伸びている。行政の都合もあり，いくつかの「拠点」と，拠点どうしを結ぶ広めの通路「公道」が定められているが，拠点と公道だけでも十分複雑なネットワークだ。

　拠点と公道を管理する当局は，モグラ市民たちの便宜を図って，公道の番号とそれが結ぶ拠点名を表にしたものを公表している。この表を入手したアリスは，地図のようなものを作れないかとヤマネの姪たちと話し合っている。

　「交差のない平面図にはとてもできそうにないわね」とアリスが言うと，「そうね，立体模型を作るといいんでしょうけど， それでは持ち運びが不便でしょうがないわ」とサンデイ。「まあ，交差があっても紙の上に描ける平面図にしましょう。でも，わかりやすくてきれいな地図にしたいから，公道で結ばれている2つの拠点は違う色に塗ることにして……」とマンデイが主張すると，チューズデイがすかさず「いいわね。でも，あんまり色数が多いとケバケバしい感じになるから，色数はなるべく少なくしたいわね」。

　それで方針は衆議一決して，地図の作製に取りかかったアリスと姪たちだが，しばらくして「ダメね。もうこれ以上には拠点の色数は減らせないわね。これより少なくすると，どこかの公道の両端が同じ色になるわ」とサタデイが言った。

　少し遠くから様子を見ていたグリフォンが「本当かい？　色数をなるべく少なくするというのはけっこう難しい問題なんだよ」と口を挟む。「きっと，間違いないわ」とサンデイ。「拠点の色の塗り分け方をずいぶんいろいろと考えてみたけど，どうやっても7色が必要みたい。でないとどれかの公道の両端の拠点が同じ色になるもの」。

　グリフォンは「フーン。7色で塗り分けできるなら，虹の7色を使えばきれいな地図が作れるね。ああ，そうだ。色数がそれ以上には減らせない場合に成り立つ事実があるよ。別にそれが成り立ったからといって，色数が最小であるという保証はないけど，少なくとも傍証にはなるだろう」と言って続ける。「7色のうちどれでも好きな2色を選ぶ。その一方の色の拠点からスタートし，公道を通って残りの5色の拠点を次々に1回ずつ巡り，最後にもう一方の色の拠点にたどり着くようなルートを探してごらん。もし拠点の色の塗り分けで6色以下のものがないなら，必ずそういうルートが存在するから」。

　アリスと姪たちはそれぞれ自分の好きな2色を選んでそのようなルート探しに取りかかったが，今月号の問題はこのグリフォンの発言の根拠を示してもらうことだ。

答えは2022年7月号に掲載