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

各辺には二つの端点があり、それぞれの端点の次数にちょうど $1$ ずつ加わる——端点ごとに一、辺ごとに二の寄与である。したがってすべての頂点について和をとると、各辺がちょうど二度数えられることになり、これが握手補題である:$\sum_{v \in V} \deg(v) = 2|E|$。

ケーニヒスベルクのグラフでは $\sum_v \deg(v) = 2 \times 7 = 14$ となり、前のステップの $5 + 3 + 3 + 3 = 14$ と一致する。この和はどんなグラフでも必ず偶数になるため、奇数次数の頂点の個数は直ちに偶数——$0, 2, 4, \dots$——にならざるを得ず、奇数にはなり得ない。奇数個の奇数項があれば総和が奇数になってしまうからである。

これは有用な検算にはなるが、それだけではオイラー路を否定するには弱すぎる。奇数次数の頂点の個数が偶数であることしか教えてくれず、ケーニヒスベルクの $4$ も確かに偶数である。次の二つのステップで、実際にこの謎を解決するより鋭い事実が示される。