特急すぺーしあ

数学が好きです。記載内容に間違い等がありましたらTwitter、コメント欄のどちらでも構いませんのでご連絡いただければ幸いです。

[tex:1 + 1 = 2]

準オイラーグラフの定理

この記事は以下の記事

mathtrain.jp

の準オイラーグラフに関しての証明を補完したときの勉強ノートです。

 準オイラーグラフの定理の証明

準オイラーグラフ \implies 次数が奇数であるものがちょうど2つ

Cオイラー路とする。Cの始点、終点の次数は奇数でなければならず、それ以外の頂点は、その頂点に入る枝と出る枝を一度ずつ通るため次数は偶数である。

 

次数が奇数であるものがちょうど2つ \implies 準オイラーグラフ

辺の数kに関する帰納法で証明する。k = 1のとき準オイラーグラフであることは自明。k \lt nのとき成り立つと仮定してk = nのときに成り立つことを示す。グラフGから、次数が奇数である頂点u(始点または終点)と、次数が偶数である頂点vを結ぶ辺Eを取り除く。これをG'とすれば、G帰納法の仮定により準オイラーグラフである(uの次数が偶数、vの次数が奇数になるため)。故にG'にはオイラーC'が存在する。C'を通って辺Eを通る(u → v)路こそがGオイラー路である。故にGは準オイラーグラフである。