オイラーグラフとカットセット

（2014年4月19日掲載）

問題

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

 補足

• オイラーグラフとは「一筆書きで各辺を必ず1回ずつ通って、一筆書きの起点に戻ることができる」グラフのことである（図1）。オイラーグラフの主要な性質として、「すべての頂点の次数が偶数である（これはオイラーグラフであることの必要十分条件）」「どの頂点から始めても上記の一筆書きができる」がある。
• （連結な無向グラフにおける）カットセットとは、グラフの辺の部分集合E'で、それらを当該グラフから取り除くと当該グラフが非連結になるようなもので、かつ極小である（E'の辺がどれか一つでも減っていると、それらを取り除いても当該グラフが非連結にはならない）ものをいう（図2）。

●───●───●　　●───●───●
│　　　│＼　　│　　│　　　│　　　│
│　　　│　＼　│　　│　　　│　　　│
│　　　│　　＼│　　│　　　│　　　│
●───●───●　　●───●───●
　　　　│　　　│　　　　　　│　　　│
　　　　│　　　│　　　　　　│　　　│
　　　　│　　　│　　　　　　│　　　│
　　　　●───●　　　　　　●───●
図1 オイラーグラフの例（左）とオイラーグラフでない例（右）

●─Ａ─●───●　｛Ａ，Ｂ，Ｃ，Ｄ｝：カットセットである
│　　　│＼　　│　｛Ａ，Ｂ，Ｃ，Ｅ｝：カットセットである
│　　　Ｂ　＼　│　｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝：カットセットでない
│　　　│　　＼│　（ＤあるいはＥが抜けてもグラフを非連結にできるため）
●───●─Ｃ─●　｛Ｄ，Ｅ｝：カットセットである
　　　　│　　　│
　　　　│　　　Ｄ
　　　　│　　　│
　　　　●─Ｅ─●
図2 カットセットの例

解答 → オイラーグラフとカットセット/解答