オイラーグラフの定理（一筆書きできる条件）とその証明
連結なグラフにおいて，
- 一筆書きして戻ってこれる 全ての頂点の次数が偶数
- （スタートとゴールが異なるような）一筆書きができる 次数が奇数であるものがちょうど2つ
例えば，日という漢字は一筆書きできますが，田という漢字はどうがんばっても一筆書きできません。
この記事では，一筆書きできる条件を示したオイラーグラフの定理について紹介します。
用語・記号の準備
一筆書きの条件
オイラーグラフの定理の証明
練習問題
用語・記号の準備
一筆書きできる条件について理解するために，グラフ理論の用語を説明します。
-
グラフとは，「頂点」と頂点同士をつなぐ「辺（枝）」の集合を表します。頂点の集合を ，辺の集合を と書き，グラフを と表すことが多いです。→グラフ理論の基礎
-
オイラーグラフとは，一筆書きしてもどってこれる，つまりある頂点から全ての辺を通ってもとの頂点にもどってくるような閉路が存在するグラフのことを言います（そのような閉路のことをオイラー閉路といいます）。 -
準オイラーグラフとは，(スタートとゴールが異なるような)一筆書きができる，つまりある頂点から全ての辺を通るような道が存在するグラフのことを言います（そのような道のことをオイラー路といいます）。
-
頂点の次数とは，その頂点から出ている辺の数を表します。
-
連結とは，全ての頂点どうしが何本かの辺を通って行き来できることをいいます（任意の2頂点の間に道がある）。
一筆書きの条件
「日」や「田」くらいなら一筆書きできるかどうか試せば分かりますが，もっと大きなグラフになると判断するのは難しそうですね。
そこで使えるのが，冒頭でも述べたオイラーグラフに関する定理です。
連結なグラフにおいて，
- オイラーグラフ 全ての頂点の次数が偶数
- 準オイラーグラフ 次数が奇数であるものがちょうど2つ
各頂点の次数が偶数なのか奇数なのかを数えていけば一筆書きできるかどうか分かるという定理です。
図のようなグラフは一筆書きできるか？
上の図では，次数が3の点が2つ（青い点）で残りの頂点の次数は偶数なので準オイラーグラフです（実際に青い点から始めれば一筆書きできるので試してみてください）。
オイラーグラフの定理の証明
「オイラーグラフ 全ての頂点の次数が偶数」を証明します。証明の途中で実際に一筆書きの方法も構成しています。
をオイラー閉路とする。 において頂点 が現れたら， に入る枝と出る枝を通るので，1回につき2つの枝を通る。全ての枝を1度通るので の次数は偶数となる。
辺の数 に関する帰納法で証明する。全ての頂点の次数が偶数なので であり， のときにオイラーグラフなのは自明。 のとき定理を仮定して のときも成立することを証明する。
全ての頂点の次数が偶数のときグラフ は閉路 を持つ（行き止まりがないので，適当な頂点からスタートしてつながった点に移動していけばいつかは通った点のどこかに戻ってくる）。 から を除いたグラフを と書く。
帰納法の仮定より， の各連結成分 にはオイラー閉路 が存在する。 をまわりつつ との共通点に到達したら を一周してもとの頂点にもどってくることで一筆書きが構成できる（図参照:オイラー閉路は，）。
※連結成分とは，極大で連結な部分グラフのことをいいます。「島」をイメージしていただきたいです。
後半はわりと長い証明になってしまいましたが，厳密にやろうとするとこのようになります（他のいくつかのサイトでは間違っている証明が載っていました）。
また，準オイラーグラフに関しても同様に証明できます。
練習問題
日という漢字は一筆書きできて，田という漢字はどうがんばっても一筆書きできないことを確認せよ。
- 日は次数が3の頂点が2つあるので，準オイラーグラフ。
- 田は次数が3の頂点が4つあるので，オイラーグラフでも準オイラーグラフでもない。
これで一筆書きできるか簡単に判定できます。
Tag:数学的帰納法のパターンまとめ