ケーニヒスベルクの7つの橋

18世紀、ケーニヒスベルクという町の人々は、ある謎解きに長い間頭を悩ませていました。町にはプレーゲル川が流れていて、川の中に二つの島ができています。この川には、島へ渡る橋が全部で7つかかっていました。日曜日の1回の散歩で、すべての橋をちょうど1回ずつ渡ることはできるでしょうか。橋がどのようにかかっていたかを見てみましょう。

どこかから散歩を始めて、すべての橋をちょうど1回ずつ渡ることはできるでしょうか。試してみましょう。左下から出発して上へ進み、それから順に右へ進んでいきます。

7つの橋のうち6つを渡りましたが、1つ渡り残してしまいました。別の道順も試してみましょう。

今度もケーニヒスベルクの7つの橋のうち、6つしか渡れませんでした。1回の散歩で、どの橋もちょうど1回ずつ渡るのは不可能なように思えてきます。ある日、この問題に有名な数学者レオンハルト・オイラーが出会いました。有名どころか、オイラーは数学の伝説ともいえる人物で、ネイピア数を e という文字で表したのもオイラーです。オイラーはこの謎を解いてみようと考えました。まず、橋が出入りしている島や町の各部分に記号をつけました。

オイラーは次のように考えました。ある島にかかる橋の数が偶数なら、どこから出発しても、1回の散歩でそれらの橋をすべて渡れます。つまり、1つの橋で島に入り、別の橋で島から出ると、まだ渡っていない橋の数は2つ減ります。1つの橋で島に入って別の橋で出るには、橋が2つ必要です。島に6つの橋がかかっていれば、その島には3回立ち寄ることになります。例えば、島Bに次のように4つの橋がかかっていたとしましょう。

この場合は、どこから出発しても、1回の日曜日の散歩ですべての橋を渡れます。試してみてください。図には道順の一つを示しました。では、島Bに、島Dからの橋がもう1つかかっていたとしたらどうでしょうか。

先ほど選んだ道順では、すべての橋をちょうど1回ずつ渡ることはできません。どれかの橋で島Bにもどり、それから島Dへ渡る必要があります。しかし、別の道順を選ぶことはできます。島Bから散歩を始めれば、すべての橋をちょうど1回ずつ渡れます。

島Bから出発し、上の地区Aへ行き、橋を渡ってBにもどり、地区Cへ行き、またBにもどって、最後に島Dへ渡りました。このように、かかる橋の数が奇数の島から出発すれば、その島の橋をすべてちょうど1回ずつ渡れます。逆に、島Dから出発して島Bで終わることもできます。

こうしてオイラーは、すべての橋をちょうど1回ずつ渡れるための条件に気づきました。すべての島にかかる橋の数が偶数であるか、または橋の数が奇数の島がちょうど2つであることです。奇数の島の一方から出発し、もう一方で終わればよいのです。それ以外の島は、橋の数が偶数でなければなりません。では、ケーニヒスベルクのもとの7つの橋を見てみましょう。

すると、どの島も橋の数が奇数であることがわかります！島Aは3つ、Bは5つ、Cは3つ、Dも3つです。そのため、この謎には答えがありません。1回の日曜日の散歩で、7つの橋すべてをちょうど1回ずつ渡ることはできないのです。ただし、どれか1つの橋を取り壊せば、とたんに答えが見つかるようになります。例えば、島Bと島Cを結ぶ橋の1つを取り壊してみましょう。

島Bの橋は4つ、島Cの橋は2つになりました。島Aと島Dの橋の数は変わりません。これで、橋の数が偶数の島が2つ、奇数の島が2つになりました。橋の数が奇数の島の一方から散歩を始めれば、すべての橋をちょうど1回ずつ渡れます。図では、島Aから出発して島Dで終わっています。

こうしてレオンハルト・オイラーはまた一つ有名な数学の問題を解き、現在グラフ理論と呼ばれている分野の基礎を築いたといえます。オイラーにちなんで、グラフ理論では、すべての辺をちょうど1回ずつ通れる（一筆書きができる）グラフをオイラーグラフといいます。