公道巡り（問題）

　無限モグラ国は，地表は真っ平らで，地平線のかなたまで整然とした区画に分かれており，区画ごとに異なる色の花々が美しく咲いている。だが，地下となるとまったく様相が異なる。くねくねと曲がるトンネル通路が上下東西南北あらゆる方向に縦横無尽に走っていて極めて複雑だ。

  通路の幅も長さもまちまちだが，それでも多少は整理しようという行政の意向で，いくつかの「拠点」と，拠点どうしを結ぶ広い通路「公道」が定められ，当局によって管理されている。一方，公道以外の通路は「私道」と呼ばれている。

　住人たちは無限匹いるので私道は無限にあるが，公道は有限本しかなく，それぞれが2つの拠点を直接結んでいる。そして管理の都合上，すべての公道には1番からの通し番号がついている。念のため断っておくが，同じ拠点を結んでいるような無意味な公道は存在しない。

　人間と同様，モグラの若者たちも出会いを求めて，あるいは自分探しのためにいろいろな場所に出かけていたのだが，それに飽きたのか，最近は奇妙な条件付きの旅が流行っているという。その条件とは，公道番号がだんだん大きくなるようになるべくたくさんの公道を巡るというものだ。もちろん，それらの公道は拠点で直接つながっていなければならず，ある拠点から別の拠点へ私道を使って行くのは反則だ。

　1つの拠点からは通常，何本もの公道が出ているが，各拠点から出ている公道の本数の平均値をdとする。今月号の問題は「『拠点』と『公道』のネットワークがどうなっていようと，d本以上の公道からなる経路で公道番号が次第に大きくなっていくものが必ず存在すること」を証明することだ。

　ここで経路というのは，もちろん拠点を介して互いにつながった公道の列のことであるが，途中で同じ拠点を繰り返し通ってもよいし，出発拠点と到達拠点は同じでも異なっていてもかまわない。