定理証明済み
オイラー回路に関するオイラーの定理
内容
連結な有限多重グラフがオイラー回路（すべての辺をちょうど一度ずつ通る閉じた歩道）を持つための必要十分条件は、すべての頂点の次数が偶数であることである。
なぜ正しいのか?
歩道がまだ使っていない辺を通ってある頂点に入るたび、別のまだ使っていない辺を通って出て行かなければならず、その頂点に接続する辺は二つずつ対になって消費される。すべての頂点に偶数本の辺があれば、出発点に戻ったときを除いて途中で行き詰まることは決してなく、残ったループも主たる巡回路に継ぎ足すことができる。
証明の概略
必要性は、頂点を訪れるたびに接続する辺を二本（入る辺と出る辺）使うことから直ちに従う。十分性については、任意の頂点から出発して使っていない辺をたどり、行き詰まるまで進む。次数がすべて偶数であることから、行き詰まり得るのは出発頂点に限られ、閉じた小道ができる。まだ使っていない辺が残っていれば、連結性によりその小道上のどこかの頂点に未使用の接続辺がある。残余グラフ（依然としてすべての次数が偶数）の中でそこから別の閉じた小道を作って継ぎ足す操作を、すべての辺を使い切るまで繰り返す。
この定理を使うトピック
関連する定理
ステップごとの証明
この定理のステップごとの証明はまだありません。
参考文献
- Leonhard Euler (1741). Solutio problematis ad geometriam situs pertinentis · DOI:10.1090/spec/098/33