解法：欧拉的度数论证(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$ 确实是偶数。接下来两步将给出真正解决这个谜题的更精确事实。