Document

演習解答（１/３）
6-1
1. 共通の辺 e から辺をたどり，はじめ
て２つの閉路が分かれる点を a と
b
a
e
する．a から一方の閉路をたどり，
はじめてもう一つの閉路と合流する
点を b とする．右図より，a と b を結
ぶ a, b 以外の頂点がすべて異なる道が２つ存在し，
それは辺 e を含まないので，e を含まない閉路（赤）が存在する．
2. G が半オイラーグラフ
⇔ G の辺をすべて含む閉路ではない小道が存在
⇔ G は辺を一つ追加してオイラーグラフにできる … (＊)
⇔ G には奇数次の点が２つだけ存在
注意：（＊）で，追加する辺は，半オイラー小道の始点と終点を
結ぶ辺であり，これは，２つの奇数次の点を結ぶ辺．
6-2
演習解答（２/３）
3. 頂点数が n の完全グラフ Kn の頂点の次数は n – 1 であるから，
頂点数が奇数の完全グラフがオイラー・グラフである．たとえば，
K3，K5．
K3
K5
K2 が半オイラー・グラフである．
２つの点のみが奇数次の点で，残りの点は偶数次の点であるも
のが，半オイラー・グラフである（問題２より）．K2 はこの条件を満
たす．しかし，n ≥ 3 の Kn はすべての頂点（3つ以上）が奇数また
は偶数となりこの条件を満たさない．
6-3
演習解答（３/３）
4. u に戻ったのであるから，この時点で残っているグラフにおいて，
すべての点の次数は偶数である．
v が橋 vw に接続しているとする（下図）．vw を除去した場合，w
が含まれる成分のグラフを K とする． vw を除去する前はすべて
の点の次数が偶数であるから，K においては，w の次数のみが
奇数である．これは系4-2に矛盾する．
v (=u)
K
w

Download Report