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

各辺をちょうど一度ずつ渡る経路があるとしよう。頂点 $v$ を一つ固定し、経路が旅の途中で $v$ を訪れるたび(つまりその訪問において $v$ が最初でも最後でもないとき)を見る。そのような訪問はそれぞれ、$v$ に到着するために一本の辺を使い、再び $v$ を出発するために別の一本の辺を使う。経路は辺を二度使わないため、$v$ における辺が異なる訪問間で再利用されることはない。

これにより、経路全体の始点でも終点でもない訪問のたびに、$v$ における辺は(到着,出発)のペアとして二本ずつ対になる。$v$ が始点にも終点にもならなければ、そのすべての辺がこのように対になるため、$\deg(v)$ は偶数でなければならない。$v$ が始点である(かつ終点ではない)場合、対応する到着のない出発の辺が一本残るため $\deg(v)$ は奇数になる。対称的に、$v$ が終点のみである場合は対応する出発のない到着の辺が一本残る。$v$ が始点かつ終点(閉じた周遊)である場合、残った出発の辺と残った到着の辺が互いに対になり、$\deg(v)$ は再び偶数になる。

一つの経路には始点と終点がそれぞれちょうど一つずつある(同じ頂点であってもよい)ため、この対応づけの議論は、グラフの頂点のうち奇数次数になり得るのは高々二つであり、経路が閉じている場合は一つもないことを直接示している。これがオイラーの規則の背後にある実際の仕組みであり、単に鵜呑みにすべき事実ではない。