出題・補足 → [[オイラーグラフとカットセット]]

!!!問題（再掲）

Gを連結な無向グラフとする。Gがオイラーグラフであるための必要十分条件は、Gの任意のカットセットが偶数本の辺からなることであることを示せ。

!!!証明

!!Gがオイラーグラフである ⇒ Gの任意のカットセットが偶数本の辺からなる

結論の否定、すなわち「Gのカットセットで、奇数本の辺からなるものが存在する」を仮定する。このとき、カットセットによってGは二つの部分に分けられるので、それをG1とG2とする。

さて、G1とG2の間には奇数本の辺のみが存在するので、G1から一筆書きを始めて、このカットセットをなす辺をすべて通ったとすると、一筆書きはG2側で終了する。これはGがオイラーグラフであることに矛盾する。よって、Gの任意のカットセットは偶数本の辺からなる。

 カットセットの辺が3本の例。
 ★を起点として、全辺を1回ずつ
 通るような一筆書きをすると…
 ┌────┐　　┌────┐
 │　★　　│　　│　　　　│
 │　　　　├──┤　　　　│
 │　Ｇ１　├──┤　Ｇ２　│
 │　　　　├──┤　　　　│
 │　　　　│　　│　　　　│
 └────┘　　└────┘

 ☆に来た時点で、もう★に戻る
 辺は存在しない！
 ┌────┐　　┌────┐
 │　★　　│　　│┏┓　　│
 │　┗━━┿━━┿┛┃　　│
 │Ｇ１┏━┿━━┿━┛Ｇ２│
 │　┏┛┏┿━━┿☆　　　│
 │　┗━┛│　　│　　　　│
 └────┘　　└────┘

!!Gの任意のカットセットが偶数本の辺からなる ⇒ Gがオイラーグラフである

Gの任意のカットセットが偶数本の辺からなるということは、Gの任意の1点とそれ以外を分けるようなカットセットも必ず偶数本の辺からなる。

さて、「Gの1点とそれ以外を分けるようなカットセットが偶数本の辺からなる」というのはすなわち、その点の次数が偶数であることを意味する。しかもそれがGのすべての頂点について成り立つので、Gがオイラーグラフである必要十分条件「Gのすべての頂点は次数が偶数である」もいえる。