公道巡り（解答）

　奇妙な印象の問題だ。dは各拠点から出ている公道の本数の平均値だから，経路の長さ（ここでは経路の物理的な道のりではなく，経路を構成する公道の本数を経路の長さと呼ぶ）とは一見無関係な気がする。しかし，このパズルは，あまり知られていないようだが，グラフ理論で定理として述べられるある事実をもとにしたものである。

　グラフ理論では，頂点とそれをつなぐ辺からなる図形のことを「無向グラフ」と呼ぶ。無限モグラ国の地下にある拠点を頂点，公道を辺と考えると，拠点と公道のネットワークは無向グラフと見なせる。一般の無向グラフでは，同一の頂点を結ぶ辺があることもあり，それらをループと呼ぶが，この問題ではループは存在しない。各頂点に入ってくる（あるいは各頂点から出ていく）辺の本数をその頂点の「次数」と呼び，問題のdはそれぞれの拠点の次数の平均だ。

　実は，dは頂点の数nと辺の数mから簡単に求められる。各辺がそれぞれ2つの頂点を結んでいるから，すべての辺では延べ2m個の頂点を結んでいる。従って2mはすべての頂点の次数の合計に等しいから，平均次数dは2m/nだ。

　さて，次のように考えることで，その平均次数dと，公道番号が昇順に進む経路の長さとの間に，不思議とも当然とも思える関係が生じる。

　まず，nカ所の拠点すべてに若者モグラを1匹ずつ配置することにしよう。そのモグラたちに次のような手順で旅をさせる。公道には1番から順に番号が振られているから，まず1番の公道が結ぶ拠点に配置された2匹のモグラにそこを通って位置を交換するように指示する。他のn−2匹は動かさない。次に，2番の公道の両端にいる2匹のモグラに位置を交換させる。さらに，3番の公道の両端にいるモグラ……という具合に順にm本すべての公道にわたって同様に進める。最終的には，若者モグラたちはその位置を入れ替えただけで，すべての拠点に1匹ずつ配置されていることは最初と変わらない。

　まず，この一連の指示に従って進んだn匹のモグラたちのどの経路も，公道番号が昇順になっていることに気づかれたい。次に，このn本の経路の長さの総和はいくつだろうか？　これは簡単だ。1回の指示によって移動するモグラは2匹だけだ。従って，m回の指示によって動いた延べ回数は2mで，これが全経路を構成する公道の延べ本数，すなわち経路長の総和でもある。経路は全部でn本あるから，経路長の平均は2m/nであり，平均次数dに等しい。従って，経路の中には長さがd以上のものが存在する。