つーさのくーかん

綺麗なモノには目がないつーさです。

ある国にはいくつかの空港があります。
どの空港からも国内便は3本しか出ていません。
しかし、どの空港から出発しても、直行便または１回の乗り換えで、
他のすべての空港に行くことができます。
さて、最大で空港は何カ所設置できるでしょうか。

かのピーター・フランクル氏が書いた「頭のよくなる本」に出てた問題なのですが。

解答例としては……

直行便で行ける空港は３カ所。
そこから乗り換えていける空港は２カ所(戻らないから)。
そこに出発点の空港を足して、3+3*2+1 = 10 カ所。

これが答えなのですが、それはともかく、それを実現する空路マップの例として
「ペテルセン・グラフ」というのがあるのです。

グラフの魅力、あなたにはわかってもらえますか？

で、本の答えの続きに書いてあったんですが。
国内便の本数を「３」から「７」にした時も、対象な構造が得られるそうなんです。
どんな接続を行えばいいのかも見えてこないのですが、一目見てみたいなと思った次第です。

(というわけで、つづくかも)