与えられた画像にある問題は以下の通りです。 * 7.3節(p.80)の7.12: 図7.11(a)のグラフGにおいて、(1) $x$と$z$を結ぶ長さ4の道、(2) $x$と$z$を結ぶ長さ5の小道、(3) $x$と$z$を結ぶ長さ3の歩道を求めよ。 * 7.4節(p.84)の7.15: 図7.13のグラフGのオイラー回路を示せ。 * 7.4節(p.84)の7.17のうち、グラフGのハミルトン閉路を示せ。 * 追加問題: 教科書p.84 図7.17(b)のグラフHにオイラー回路がないことをオイラーの定理を用いて示せ。

1. 問題の内容

与えられた画像にある問題は以下の通りです。

* 7.3節(p.80)の7.12: 図7.11(a)のグラフGにおいて、(1) $x$と$z$を結ぶ長さ4の道、(2) $x$と$z$を結ぶ長さ5の小道、(3) $x$と$z$を結ぶ長さ3の歩道を求めよ。

* 7.4節(p.84)の7.15: 図7.13のグラフGのオイラー回路を示せ。

* 7.4節(p.84)の7.17のうち、グラフGのハミルトン閉路を示せ。

* 追加問題: 教科書p.84 図7.17(b)のグラフHにオイラー回路がないことをオイラーの定理を用いて示せ。

2. 解き方の手順

* 7.12: グラフGの図7.11(a)を見ながら、$x$から$z$への道、小道、歩道を数え上げます。道は同じ頂点を2度通らない経路、小道は同じ辺を2度通らない経路、歩道は頂点、辺に関わらず同じものを何度通っても良い経路です。

* 7.15: グラフGの図7.13を見ながら、すべての辺をちょうど一度だけ通る閉路を探します。それがオイラー回路です。

* 7.17のうちグラフGのハミルトン閉路: グラフGの図7.17(a)を見ながら、すべての頂点をちょうど一度だけ通る閉路を探します。それがハミルトン閉路です。

* 追加問題: グラフHの図7.17(b)を見ながら、オイラーの定理（オイラー回路が存在するための必要十分条件は、グラフが連結であり、すべての頂点の次数が偶数であること）を使って、オイラー回路が存在しないことを示します。

3. 最終的な答え

* 7.12:

(1) $x$と$z$を結ぶ長さ4の道: $x-c-d-e-z$

(2) $x$と$z$を結ぶ長さ5の小道: $x-c-b-u-w-z$

(3) $x$と$z$を結ぶ長さ3の歩道: $x-c-z$

* 7.15: オイラー回路の一例: $a-b-c-d-e-f-a$

（他にも多数存在します）

* 7.17のグラフGのハミルトン閉路: $a-b-c-d-e-f-g-h-i-a$

（他にも多数存在します）

* 追加問題:

グラフHにおいて、頂点a, c, d, f, g, iの次数は3であり、奇数です。

オイラーの定理によれば、グラフにオイラー回路が存在するためには、すべての頂点の次数が偶数である必要があります。

したがって、グラフHにはオイラー回路は存在しません。