解法: オイラーの次数による論証(1736年)

オイラーは各土地を頂点に、各橋をそれが結ぶ二つの土地を結ぶ辺に置き換え、地図を $|V| = 4$ 個の頂点と $|E| = 7$ 本の辺を持つグラフ $G = (V, E)$ に変換する。各橋をちょうど一度ずつ渡る散歩は、$G$ の中で各辺をちょうど一度ずつ使う経路になる——これが現在オイラー路と呼ばれるものである。

ケーニヒスベルク市(現在のプレーゴリャ川沿いのカリーニングラード)は二つの島と二つの川岸からなり、七つの橋で結ばれていた。市民たちはすべての橋をちょうど一度ずつ渡れるかどうかを議論しており、レオンハルト・オイラーはこの謎を耳にし、1736年にサンクトペテルブルク科学アカデミーで発表した短い論文の中で、通りや橋の正確な形は問題に無関係であり、どの橋がどの土地を結んでいるかという結びつきのパターンだけが重要だと指摘した(Biggs, Lloyd & Wilson 1976, 第1章)。

地理からグラフ $G$ へのこの変換こそが本質的な第一手である。以降のすべてのステップは点と線からなる抽象的な図を扱い、これから展開する議論はケーニヒスベルクに限らず、この形で配置された任意の橋の集合に当てはまる。