二つの島、二つの岸、七つの橋。橋を岸ごとに数えると 3、3、3、5 になり、次数の和は 3 + 3 + 3 + 5 = 14 です(一つ目のリンク。三つ目のリンクは同じ 14 を 3 × 3 + 5 として得ます。より速い括りです)。この和の半分が橋の数です——二つ目のリンクは 7 に割ります——そしてこの関係はこの地図に特別なものではありません:各橋は二つの岸に寄与するので、次数は辺の数の二倍でなければなりません。四つ目のリンク 4 × 3/2 = 6 は橋で結べる陸地の組の数で、六つの組に七つの橋があるので、少なくとも一組の陸地は一つではなく二つの橋で結ばれます。
オイラーの論法は、各橋を一度渡る散歩は、通過する各陸地に組で入り組で出ねばならない、つまり立ち寄りに使う各節点は偶数次数を持つ、ということです。散歩の最初と最後の節点だけが例外で、それは二つしかありません。ケーニヒスベルクには四つの奇数節点があるので、要求された種類の散歩は存在せず、証明は誰かが川を測量する前に完成しています。これがこの仕事がパズルの解ではなくグラフ理論の最初の定理として扱われる理由です:距離、岸の形、プレーゲル川の幅はすべて無関係であり、オイラーは問題を大きさの幾何ではなく位置の幾何に置くことでそう言っています。七つの橋のうち二つは 1944 年に破壊され再建されなかったので、今や問いは観光上のものです。ここの算術は 1735 年にオイラーへ送られた地図に関するものです。
答え
14
読み方
四つの次数の和。二つ目のリンクはそれを半分に割って七つの橋に、三つ目は別の括りで同じ和、四つ目は陸地の組を数えます。
出典
Leonhard Euler, 'Solutio problematis ad geometriam situs pertinentis', 1736, the founding paper of graph theory; the Königsberg bridges on the Pregel were seven in Euler's map, two of which were destroyed in 1944 and not rebuilt
電卓で解いてみる
これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。