解法: オイラーの次数による論証(1736年)
ざっくり言うと
各土地が一つの点になった今、その点にいくつの橋の線が触れているかを数えよう——この数を点の次数と呼ぶ。ある土地に立ってそこから伸びるすべての橋を見渡していると想像すれば、次数はまさに次の一歩に選べる選択肢の数を表している。
詳しい解説
頂点の次数とは、その頂点に接続する辺の数である。史実の橋の配置から次数を読み取ると、中央の島 (クナイプホーフ)には 本の橋があり、他の三つの陸地 にはそれぞれ 本の橋がある。
Biggs, Lloyd & Wilson(1976年、第1章)に再録されているオイラー自身の図は、二つの川岸と二つの島に印を付け、七つの橋を一つずつ列挙している。それぞれの土地に触れる橋の数を足し合わせると、まさに上記の次数が得られ、合計 は次のステップで重要になる。
- 頂点の次数
- 頂点 に接続する辺の数で、 と表す。このグラフではある土地に触れる橋の数がそのまま次数になる。