オイラーグラフの十分条件について

質問

グラフ理論についての質問です。よろしくお願いします。

「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」
を証明したいです。
「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。
（最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました）
また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。
非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？

以上になります。ご教示いただければ幸いです。

回答No.1

nakaken88 · ベストアンサー

まず、「Gは連結」というのは、本のだいぶ前の方で前提としているのではないかと思います。質問に書かれているとおり、連結でないと成り立ちません。

さて、オイラーグラフになることの証明ですが、「グラフGが連結で、Gのすべての頂点の次数が偶数なら、Gはオイラーグラフとなる」という定理を使い、各頂点の次数が偶数であることを示すことにします（この定理はオイラーの定理として有名なので、おそらく教科書にも載っているはずです。なので使ってしまいます）。

vをグラフGの任意の頂点とします。vに接合する辺をe(1),…,e(n)とおきます。e(i)を含むサイクルは必ずvを含みます。また、vを含む各サイクルには、e(1),…,e(n)のうちのどれか偶数個が含まれます。つまり、Σ（e(k)を含むサイクルの数） は偶数になることがわかります。

ここで、e(k)を含むサイクルの数は仮定から奇数個なので、辺の個数nは偶数でないといけません。よって、Gのすべての頂点の次数は偶数となり、Gはオイラーグラフとなります。

お礼

早速のご回答ありがとうございます。

＞本のだいぶ前の方で～
自分もそう思って章や節の冒頭を読み返したのですが、連結性についての記載は見当たりませんでした。
自明な前提として省略した、あるいは単に記載漏れだった、ということで納得しようと思います。

＞オイラーの定理
証明つきで紹介されているので、使って問題ないと思います。
その旨を一言添えておけば良かったですね。失礼いたしました。

＞証明
なるほど、任意の頂点について接合する各辺が含まれるサイクルの数の和が偶数になる、という話にもっていくのですね。
次数が偶数になることを示す、というのは考えたのですが、流れがまとまらず断念していました。

とてもすっきりしました。分かりやすいご回答ありがとうございました！