next up previous
Next: この文書について... (PDF ��������: euler.pdf)

平成 13 年 6 月 28 日
オイラー閉路に関する定理の証明
新潟工科大学 情報電子工学科 竹野茂治

教科書 p.97-98 に、全ての頂点が偶数次ならオイラーグラフであることの 証明が載っているが、その証明はやや難しい。 よって講義では、帰納法による構成的な証明を紹介したつもりであった (06/28 2001) が、その証明には穴があった。

よって、改めて厳密な証明を紹介する。


補題 1

全ての頂点の次数が偶数次ならば橋はない。


証明

もし、頂点 $u_1$ と $u_2$ を結ぶ辺 $e$ が橋であるとすると、$e$ を 取り除いたグラフは連結でなくなる。そのグラフの $u_1$ を含む 連結成分は、$u_1$ 以外の頂点の次数は偶数のままで、$u_1$ の頂点のみが 奇数次数となる。よって、それは握手補題 (教科書 p89 問題 3.1) に矛盾する。



定理 2

全ての頂点が偶数次である連結なグラフはオイラーグラフである。


証明

辺の数 $\vert E\vert$ に関する帰納法で証明する。

[I] $\vert E\vert=1$ のとき
定理の条件を満たすグラフは、この場合ループのみであり、 これはもちろんオイラーグラフ。

[II] $\vert E\vert=k\geq 2$ のとき
$\vert E\vert=k-1$ であるようなグラフに対しては、この定理は成り立っていると 仮定する。

このグラフの一つの頂点 $u_1$ を考える。$u_1$ の次数は偶数なので 少なくとも 2 本の辺がつながっている。その $u_1$ につながる辺の 状態を次のように場合分けして考える。

  1. ループがある場合
  2. (i) でなくて $\deg(u_1)=2$ で $u_1$ から 2 重辺が出ている場合
  3. (i) でも (ii) でもなくて $\deg(u_1)=2$ である場合、つまり $u_1$ から他の 2 点への辺が 出ている場合
  4. (i)$\sim$(iii) ではなく $u_1$ から 3 重以上の辺、あるいは 2 重辺が 2 組以上出ている場合
  5. (i)$\sim$(iv) ではなく $\deg(u_1)\geq 4$ で、$u_1$ から 2 重辺は一つしか出ていない場合
  6. (i)$\sim$(v) ではない場合、 すなわち、 $\deg(u_1)\geq 4$ で、全ての辺が異なる頂点に結ばれている 場合

  1. この場合はそのループを取り除いても、各頂点の次数が偶数であること、 連結であることには変わりはなく、辺の数だけが 1 減る。よって、 帰納法の仮定によりそのグラフはオイラーグラフである。 そのオイラー閉路が $u_1$ を通るときに、取り除いたループを通るように すればそれは元のグラフのオイラー閉路になるので、この場合は オイラー閉路であることがわかる。

  2. $u_1$ から 2 重辺が一つ $u_2$ に出ている場合を考える。 この場合は、このグラフからこの 2 重辺と $u_1$ を取り除き、 $u_2$ に一つループをつけると、$u_2$ の次数は変化なく、 連結性も変わらず、辺の数が一つ減る。 よって、帰納法の仮定によりそのグラフはオイラーグラフとなり、 そのオイラー閉路における付け加えたループの箇所を、元の 2 重辺を通る 閉路に変えれば元のグラフのオイラー閉路が構成できる。

  3. $u_1$ から $u_2$, $u_3$ への辺 $e_2$, $e_3$ が出ているとする。 このときは、このグラフから $e_2$, $e_3$ と $u_1$ を取り除き、 新たに $u_2$, $u_3$ に辺 $e'$ を付け加える。そうすると、 $u_2$, $u_3$ の次数に変化はなく、連結性も変わらず、辺の数が 一つ減る。よって帰納法の仮定によりそれはオイラーグラフであり、 その閉路の $(u_2,e',u_3)$ (または $(u_3,e',u_2)$) を $(u_2, e_2, u_1, e_3, u_3)$ (または $(u_3, e_3, u_1, e_2, u_2)$) で置き換えれば元のグラフのオイラー閉路ができる。

  4. まず、$u_1$ から $u_2$ への 3 重辺がある場合を考える。この場合は そのうち 2 つの辺を (ii) と同様にループで置き換えれば よい (すなわち、連結性、全ての頂点の次数が偶数であることは変わら ず、辺の数が 1 減り、帰納法の仮定によりオイラーグラフとなり、 そのオイラー閉路でその置き換えを逆にして元のグラフのオイラー閉路 が作れる) 。

    次に、$u_1$ から $u_2$ への 2 重辺と、$u_3$ への 2 重辺の 2 組が出ている場合はそれぞれから 1 辺ずつ取り除いて (iii) のように $u_2$ と $u_3$ を結ぶ辺を作ればよい (連結性、次数の偶数性は 変化なし)。

  5. 次数は $\deg(u_1)\geq 4$ なので、$u_1$ から $u_2$ への 2 重辺以外に $u_1$ から他の頂点 $u_3$ への辺 $e$ もある。この $e$ と 2 重辺から 1 本を取り除いて (iii) のように $u_2$ と $u_3$ を結ぶ 辺を作れば良い。連結性が問題となるが、$e$ は補題 1 により 橋ではなく、これを取り除いても連結のまま、そして、2 重辺から 1 本取り除いても連結性は変わらないので OK.

  6. $u_1$ から $u_2$, $u_3$, $u_4$, $u_5$ へそれぞれ辺 $e_2$, $e_3$, $e_4$, $e_5$ が出ているとする。 この場合も (iii) のようにしたいが、例えば $e_2$, $e_3$ を 取り除いて $u_2$, $u_3$ を結ぶ辺を付け加えたときに、 グラフが連結でなくなる場合が問題となる。

    もし、$e_2$, $e_3$ を取り除いて $u_2$, $u_3$ を結ぶ辺 $e'$ を つけたときに連結であるか、 あるいは、$e_4$, $e_5$ を取り除いて $u_4$, $u_5$ を結ぶ辺 $e''$ を つけたときに連結であるならば、それは (iii) と 同様に考えれば帰納法の仮定により OK となる。

    よって、後は $e_2$, $e_3$ を取り除いて $e'$ をつけても、 $e_4$, $e_5$ を取り除いて $e''$ をつけても連結でなくなる場合を 考えれば良い。

    この場合、まず、$e_2$, $e_3$ を取り除いたとき、$e'$ をつけなくても $u_2$, $u_3$ を結ぶ別なパスが存在することをまず示す。

    元のグラフに橋はないので、$e_2$ を取り除いても連結のまま。 よって、$e_3$ を取り除いてはじめて連結でなくなるので、この場合 その連結成分は 2 つであり、$u_3$ は $u_1$ の属さない連結成分に 含まれる。同じ理由で $u_2$ も $u_1$ の属さない連結成分に 含まれるので結局、$u_2$ と $u_3$ は同じ連結成分に入ることになる ので、$u_2$ と $u_3$ を結ぶパスが存在する。

    同じ理由で $e_4$, $e_5$ を取り除いても、$u_4$, $u_5$ を結ぶ別な パスが存在することになる。

    ということは、元のグラフから $e_2$ と $e_4$ を取り除くと、 それは連結性は失われないことになる。後は $u_2$ と $u_4$ を結ぶ 辺を付け加えれば (iii) と同様にして帰納法により言えることになる。


やや場合分けが繁雑になるが、連結性のことを考え、このように せざるを得なかった。他の、これよりスマートな証明方法も多分 たくさんあるだろうと思われる。

例えば次のような証明も思いついた。こちらの方が、より具体的な一筆書きの 問題の解答に近い。帰納法の [II] から先を進める。

証明

[II] $\vert E\vert=k\geq 2$ のとき
$\vert E\vert<k$ であるようなグラフに対しては、この定理は成り立っていると 仮定する。

$u_1$ からループが出ている場合は上と同じようにループを取れば 帰納法の仮定を使ってオイラー閉路を構成できる。

そうでない場合は $u_1$ から別な点 $u_2$ へ出る辺 $e$ がある。 $e$ は補題 1 により橋ではないので、この $e$ を抜いても $u_1$ と $u_2$ を結ぶパスが存在する。そのパスと $e$ をつなげば $u_1$ から出て $u_1$ に戻る一つのサイクルができる。元のグラフから このサイクルを削除すると ... あっ、だめ。連結でなくなる。



next up previous
Next: この文書について...
Shigeharu TAKENO
2001年 8月 9日