オイラーグラフの特徴付けと証明

全ての辺をちょうど一回通る回路が存在するとき、そのグラフはオイラーグラフであるといいます。また、そのような回路をオイラー回路といいます（慣習的にオイラー閉路と呼ばれることがありますが、閉路は各頂点の次数が2ですから語義としては誤りです）。

オイラーグラフであることの必要十分条件は、次の通りです：

オイラーグラフ \(\Leftrightarrow\) 連結かつ全ての頂点の次数が偶数

証明しましょう。

（\(\Rightarrow\)の証明）オイラー回路の辺を辿って一周すると、頂点を通り抜けるたびに入る辺と出る辺を1つずつ使います（始点・終点はペアにする）。従って、各頂点の次数は偶数です。また、回路は連結なので、元のグラフ \(G\) も連結です。

（\(\Leftarrow\)の証明）辺の数 \(||G||\) に対する数学的帰納法で示します。\(||G||=0\) つまり辺が存在しなければ、1頂点のオイラー回路が取れます。\(||G||\geq 1\) とします。各頂点の次数が偶数なので、DFSにより回路 \(W\) が取れます。\(G-W\)の各頂点は次数が偶数なので、帰納法の仮定より、各連結成分でオイラー回路が取れます。元のグラフ \(G\) の連結性より、各連結成分のオイラー回路は、回路 \(W\) と繋ぎ合わせることで、一つの回路にできます。これはオイラー回路そのものです。

この証明はオイラー回路を求めるアルゴリズムも示しています。DFSで極大な回路として \(W\) を取ると、通った辺の全てを \(W\) に使えます（まだ通っていない辺が接続している限り、小道を閉じずにその辺を通ります）。各辺を一度しか通らず、回路の合体も \(O(1)\) なので、\(O(E)\) でオイラー回路が構築できます。

Noga Alon の二部グラフの辺彩色
- オイラー回路が一つのカギになったアルゴリズムです。

参考文献

[1] A First Course in Graph Theory
[2] グラフ理論（R. Diestel）

Euler の名前が冠されていますが、彼が示したのは必要性（\(\Rightarrow\)）だけでした。十分性（\(\Leftarrow\)）を示したのは、Hierholzerです[1]。Euler & Heirholzerグラフと呼ぶべきかもしれません。