オイラーグラフの定理とその証明

更新日時 2021/03/07

一筆書きの条件：

連結なグラフにおいて，

オイラーグラフ⇔全ての頂点の次数が偶数

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

用語・記号の説明
オイラーグラフの定理の証明

用語・記号の説明直感的に当たり前でしょうもない用語も含まれていますが，きちんと定義しておきます。
グラフとは，「頂点」と頂点同士をつなぐ「辺（枝）」の集合を表します。頂点の集合を VVV，辺の集合を EEE と書き，グラフを G=(V,E)G=(V, E)G=(V,E) と表すことが多いです。
オイラーグラフとは，一筆書きしてもどってこれる，つまりある頂点から全ての辺を通ってもとの頂点にもどってくるような閉路が存在するグラフのことを言います。（そのような閉路のことをオイラー閉路といいます）
準オイラーグラフとは，一筆書きできる，つまりある頂点から全ての辺を通るような道が存在するグラフのことを言います。（そのような道のことをオイラー路といいます）
頂点の次数とは，その頂点から出ている辺の数を表します。
連結とは，全ての頂点どうしが何本かの辺を通って行き来できることをいいます（任意の2頂点の間に道がある）。
上の図ぐらいならぱっと見た時に一筆書きできるかどうか分かりますが，もっと大きなグラフになると一筆書きできるか判断するのは難しそうですね。
しかし，オイラーグラフに関する定理を使えば，
各頂点の次数が偶数なのか奇数なのかを数えていけば一筆書きできるかどうか分かるのです。例えば上の図では，次数が3の点が2つ（青い点）で残りの頂点の次数は偶数なので準オイラーグラフです。（実際に青い点から始めれば一筆書きできるので試してみてください）

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

「オイラーグラフ⇔全ての頂点の次数が偶数」を証明します。証明の途中で実際に一筆書きの方法も構成しています。

「オイラーグラフ→次数が偶数」の証明

$C$ をオイラー閉路とする。 $C$ において頂点 $v$ が現れたら， $v$ に入る枝と出る枝を通るので，1回につき2つの枝を通る。全ての枝を1度通るので $v$ の次数は偶数となる。

「次数が偶数→オイラーグラフ」の証明

辺の数 $k$ に関する帰納法で証明する。全ての頂点の次数が偶数なので $k\geq 2$ であり， $k=2$ のときにオイラーグラフなのは自明。 $k < n$ のとき定理を仮定して $k=n$ のときも成立することを証明する。

オイラーグラフの証明

全ての頂点の次数が偶数のときグラフ $G$ は閉路 $C$ を持つ。（行き止まりがないので，適当な頂点からスタートしてつながった点に移動していけばいつかは通った点のどこかに戻ってくる。） $G$ から $C$ を除いたグラフを $G\setminus C$ と書く。

帰納法の仮定より， $G\setminus C$ の各連結成分 $H_i$ にはオイラー閉路 $C_i$ が存在する。 $C$ をまわりつつ $H_i$ との共通点に到達したら $C_i$ を一周してもとの頂点にもどってくることで一筆書きが構成できる。（図参照:オイラー閉路は， $0,1,2,0,3,4,5,6,7,4,8,9,10,8,10,0$ ）

※連結成分とは，極大で連結な部分グラフのことをいいます。「島」をイメージしていただきたい。

後半はわりと長い証明になってしまいましたが，厳密にやろうとするとこのようになります。（他のいくつかのサイトでは間違っている証明が載っていました。）

また，準オイラーグラフに関しても同様に証明できます。

これで一筆書きできるか簡単に判定できます。

Tag:数学的帰納法のパターンまとめ