ケーニヒスベルクの７つ橋問題は解決可能か？

　中世ドイツのケーニヒスベルク（現在はロシアのカリーニングラード）を流れるプレーゲル川には、隣接した中州が２つあった。川の両岸と２つの中州は、合計７つの橋で結ばれていた。

　そして市民の間では、この７つの橋を、同じ橋を２度通らずに全て渡れるか、という遊びがあった。しかし、成功した者はいない。

　この問題に着目したのが、ペテルブルクの数学者レオナルド・オイラーだった。彼は１７３６年、これを解く長大な論考を記し、後にグラフ理論と呼ばれるようになる、数学の新たな分野を開いた。

　オイラーは、橋から到達できる陸上の地点を全て繋いで経路を示した。こうして複雑な図形、グラフが出現した。すなわち、複数の点が“エッジ”という線で結ばれた図形である。グラフの全ての路を１度だけ通る路が、「オイラー路」である。

　簡潔に結論を述べるなら、この問題は解決不能である。オイラー路が可能になるのは、奇数本のエッジで結ばれた頂点が２つ以下の場合のみだが、このケースだと２つより多いからだ。

　似たような問題で、子供向けのもある：開いた状態の封筒は一筆書きできるが、閉じた封筒はできない。開いた状態の封筒では奇数の頂点が２つ（数字の３）あるが、閉じた封筒の場合は４つだ。

　オイラーのこの発見は、電気工学、地形学、エネルギー理論などに応用されている。

　なお残念ながら、ケーニヒスベルクの橋問題を実際に試すことは、もはや叶わない。７つの橋のうち、現存するのはデレヴャンヌイ橋とメドーヴイ橋の２つのみ。他の橋は改修されて１つの高架橋にまとめられたか、あるいは第二次世界大戦中に失われてしまった。