グラフと一筆書き(その 4・最終回)

以下、奇数次の頂点を「奇点」と言うことにします。

(半)オイラー・グラフとなるための必要条件

G をオイラー・グラフ、または半オイラー・グラフとします。条件を満たすような小道をとり、その始点となる頂点を 、終点となる頂点を とします。G がオイラー・グラフならば です。
このとき、次のようにして、各頂点の「擬次数」を作ります。

1. 全ての頂点の「擬次数」の初期値を 0 とします。
2. の「擬次数」に 1 を加えます。
3. 以下、小道が各頂点を通過するごとに、その頂点の「擬次数」に 2 を加えます。
4. の「擬次数」に 1 を加えます。

このようにして「擬次数」を作ったとき、小道が全ての辺を一度ずつだけ含んでいることから、この数字は各頂点の(本当の)次数に一致することが分かります。そして、作り方から明らかに分かることとして、G がオイラー・グラフならば( であることから)全ての頂点の次数が偶数になり、半オイラー・グラフならば と の次数だけが奇数で、他の頂点の次数は偶数となります。従って

G が一筆書き可能なグラフならば、奇点の数は 0 または 2 である

ことが分かりました。この対偶を取れば、奇点が 4 個以上あるグラフは一筆書き不可能なことが分かります。

(半)オイラー・グラフとなるための十分条件

では逆に、どんなグラフなら一筆書きできるのか ? 実は上の事実の逆が成り立つことが知られています。*1そう、奇点の数が 0 または 2 であるグラフは、必ず一筆書き出来るのです !
特に、奇点の数が 0 ならばオイラー・グラフに、2 ならば半オイラー・グラフになることが知られています。
何故 ? と思った方は、ぜひ下記参考書を読んでみてください。予備知識をほとんど必要とせずに読める、分かりやすい本です。

グラフ理論入門

*1:証明はそれほど難しくありません。「全ての頂点の次数が 2 以上であるグラフには閉路が存在する」という補題を使えば、辺の数に関する帰納法で証明できます。