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

前のステップはすでにオイラーの基準の「必要」の半分を直接示している:連結グラフが各辺をちょうど一度ずつ渡る経路を持つならば、奇数次数の頂点の個数は $0$(経路が始点に戻る閉路の場合)、または、ちょうど $2$(その二頂点が始点と終点でなければならない開いた経路の場合)のいずれかである。

逆——連結グラフにおいて奇数次数の頂点が $0$ 個または $2$ 個であることが十分でもある——というのがより難しい半分である。オイラーは1736年の論文でこれを完全な証明なしに主張し、Carl Hierholzerが1873年に、閉じたループをつなぎ合わせることでそのような経路を構成する完全な構成的議論を与えた(Biggs, Lloyd & Wilson 1976, 第2章)。

二つの方向を合わせると、$\#\{v \in V : \deg(v) \bmod 2 = 1\} \in \{0, 2\}$ という正確な判定法が得られ、これはどんな連結グラフにも当てはまる。これこそが、この結果が一つの都市についての観察に留まらず、あらゆる可能な橋の配置を解決する本物の定理である理由である。