MathLabs

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

ステップ 6/6: ケーニヒスベルクには奇数次数の頂点が四つあるため、そのような経路は存在しない
前のステップ次のステップ
ざっくり言うと

証明したばかりの規則にケーニヒスベルク自身の橋の数を当てはめてみよう:四つの陸地のうち橋の数が奇数であるものがいくつあるかを確かめ、その個数を許される値である 00 または 22 と比較する。

#{v∈V:deg⁡(v) mod 2=1}=4∉{0,2}\#\{v \in V : \deg(v) \bmod 2 = 1\} = 4 \notin \{0, 2\}
詳しい解説

ケーニヒスベルクのグラフの四つの頂点 A,B,C,DA, B, C, D はすべて奇数次数(5,3,3,35, 3, 3, 3 はすべて奇数)を持つため、奇数次数の頂点はちょうど 44 個——00 でも 22 でもない。

前のステップの基準により、これはどこから出発してどこで終わっても、ケーニヒスベルクの七つの橋をそれぞれちょうど一度ずつ渡る経路は存在しないことを意味する。すべての経路を虱潰しに試すのではなく、まさにこの種の数え上げの論証によってこの問いを否定的に解決した1736年のオイラーの論文は、グラフ理論を生み出した論証として広く認められている。