判定法

話を有限(辺の数も頂点の数も)で連結(connected)なグラフに限りましょう。連結(connected)というのは任意の2頂点が鎖で結べるときです。このようなグラフにおいてもしオイラー路が存在するとすれば次の2つがいえます。
1)始点終点以外の全ての頂点において路にそって入ってくる辺の数と出て行く辺の数が同じはずなので、その頂点の原子価(valence, degree)は偶数でなければいけない。
2)始点と終点は原子価が奇数である(出発のときの出るだけの辺が一つ半端だから。終点についても同様)。
オイラー回路が存在すれば上のことから全ての頂点が偶数の原子価をもつことになります。
1)2)は有限で連結なグラフにおいて、オイラー路が存在するための十分条件でもあるのです。つまり1)2)が存在していればオイラー路が存在します。原子価が奇数の頂点が始点または終点になります。1)の条件を変更して、全ての頂点が偶数の原子価をもつとするなら、 1)2)はオイラー回路が存在する十分条件になります。勿論必要十分条件になります。

例 V={A,B,C,D,E,F,G}, E={s,t,u,v,w,x,y,r}, T(s)={A,E}, T(t)={E,B}, T(u)={B,C}, T(v)={C,F}, T(w)={F,D}, T(x)={A,D}, T(y)={E,F}, T(z)={E,G}, T(r)={G,F},のときオイラー回路は存在するか。

答え という図になるからE,F degreeは4他は2。全て偶数たのでオイラー回路が存在する。