１−１８．橋渡り問題と一筆書き

　大哲学者カントが生まれた町として有名なケーニヒスベルク（現在のカリーニングラード）は、プレーゲル川にまたがったおり、18世紀の初頭には、[1]のようにこの川に７つの橋がかかっていた。
　その頃、この橋を全部ただ一度ずつ渡ることができるかどうかが、この町の話題になった。ある人は不可能だと言った。ある人は実際にやったらできたと言ったが、もう一度再現することはできなかった。こうして町中の話題になっているときに、数学者のレオンハルト・オイラー（1707〜1783）がこの問題を取り上げて研究し、橋渡りが不可能であることを証明した。

　オイラーはまず、[1]の図を整理して、単純化することから始めた。[1]を[2]-Aのように橋の続き具合に注目して、橋を線で表し、ケーニヒスベルクの各地区を点で表してみると、[2]-Bのように変形することができる。このようにしても、それぞれの位置関係には変化がないことは明らかである。これによって橋渡りの問題は、Bが一筆書きできるかどうかの問題に変わってしまう。
　次に、一筆書きができるかどうかの判定をしなければならない。一筆書きしようとする図形のコーナー（分岐点）に注目すると、そこは書き始め（出発点）か、書き終わり（終点）か、中間点かのいずれかである。中間点の場合は、必ずその点に来る線と、そこから出ていく線とが対で存在しなければならない。一方、出発点と終点の場合は、両方が一致すれば線の数は偶数に、そうでなければ奇数になる。つまり、そこに集まる線の数が奇数になり得るのは、出発点と終点だけである。

[1]ケーニヒスベルクの図

[2]-A

[2]-B 単純化した図

　そこで一筆書きができるかどうかの見分け方は、次のようになる。まず、その図の各コーナーに集まる線の数を調べる。

1. [3]-Aのように（カッコ内は線の数）線が偶数だけの図形は、どこから書き始めても、一筆書きが可能である。
2. [3]-Bのように奇数の箇所が１または２の図形は、そこを出発点か終点（２箇所の場合はその両方）にすれば、一筆書きが可能である。
3. [3]-Cのように奇数の箇所が３以上なら、その図形は一筆書きすることはできない。

[3]一筆書き判定説明図

A

B

C

　ところで[2]-Bは、各点に集まる線の数は４箇所とも奇数であり、橋渡りは不可能との結論になる。