オイラーグラフの定理（一筆書きできる条件）とその証明

用語・記号の準備

一筆書きできる条件について理解するために，グラフ理論の用語を説明します。

• グラフとは，「頂点」と頂点同士をつなぐ「辺（枝）」の集合を表します。頂点の集合を $V$，辺の集合を $E$ と書き，グラフを $G=(V, E)$ と表すことが多いです。→グラフ理論の基礎

• オイラーグラフとは，一筆書きしてもどってこれる，つまりある頂点から全ての辺を通ってもとの頂点にもどってくるような閉路が存在するグラフのことを言います（そのような閉路のことをオイラー閉路といいます）。

• 準オイラーグラフとは，(スタートとゴールが異なるような)一筆書きができる，つまりある頂点から全ての辺を通るような道が存在するグラフのことを言います（そのような道のことをオイラー路といいます）。

• 頂点の次数とは，その頂点から出ている辺の数を表します。

• 連結とは，全ての頂点どうしが何本かの辺を通って行き来できることをいいます（任意の2頂点の間に道がある）。

一筆書きの条件

「日」や「田」くらいなら一筆書きできるかどうか試せば分かりますが，もっと大きなグラフになると判断するのは難しそうですね。

そこで使えるのが，冒頭でも述べたオイラーグラフに関する定理です。

各頂点の次数が偶数なのか奇数なのかを数えていけば一筆書きできるかどうか分かるという定理です。

上の図では，次数が3の点が2つ（青い点）で残りの頂点の次数は偶数なので準オイラーグラフです（実際に青い点から始めれば一筆書きできるので試してみてください）。

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

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

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

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

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

練習問題

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