グラフ理論の問題

使う判定法

連結なグラフについて、次が成り立つ。
- オイラー閉路（すべての辺をちょうど 1 回ずつ通り、始点に戻る経路）をもつ $⟺$ すべての頂点の次数が偶数
- オイラー路（すべての辺をちょうど 1 回ずつ通る経路。同じ頂点は何度通ってもよく、始点と終点は一致してもしなくてもよい）をもつ $⟺$ 奇数次の頂点が $0$ 個または $2$ 個

問題で問われているのは後者である。

手順 1：連結性の確認

$K_n$ ではどの 2 頂点も辺で直接結ばれているので、$K_n$ は連結である。よって上の判定法が使える。

手順 2：次数を求める

$K_n$ の各頂点は、自分以外の $n-1$ 個の頂点すべてと辺で結ばれているので、すべての頂点の次数は $n-1$ である。

手順 3：奇数次の頂点の個数を数える

• $n$ が奇数のとき：$n-1$ は偶数なので、すべての頂点が偶数次であり、奇数次の頂点は $0$ 個である。よってオイラー路（実際にはオイラー閉路）をもつ。
• $n$ が偶数のとき：$n-1$ は奇数なので、$n$ 個の頂点すべてが奇数次であり、奇数次の頂点は $n$ 個である。$3\le n\le 10$ で $n$ が偶数なら $n\ge 4$ なので、奇数次の頂点は $4$ 個以上になる。これは「$0$ 個または $2$ 個」に当てはまらないので、オイラー路をもたない。

手順 4：結論

$3\le n\le 10$ の奇数 $n$ を挙げると、求める $n$ は
$$n=3,5,7,9$$
である。たとえば $K_3$ は三角形なので、$1\to 2\to 3\to 1$ とたどれば 3 本の辺をちょうど 1 回ずつ通れる。また $K_5$ の頂点を $1,2,3,4,5$ とすると、$1\to 2\to 3\to 4\to 5\to 1\to 3\to 5\to 2\to 4\to 1$ とたどれば 10 本の辺をちょうど 1 回ずつ通れる（同じ頂点を何度も通っている）。

連結グラフがオイラー路をもつための必要十分条件は、次数が奇数の頂点の個数が 0 または 2 であることである。$K_n$ は連結で、すべての頂点の次数は $n-1$ である。

・$n$ が奇数のとき、$n-1$ は偶数なので、奇数次数の頂点は 0 個。よってオイラー路（実際にはオイラー閉路）が存在する。
・$n$ が偶数のとき、すべての $n$ 個の頂点の次数が奇数になる。$n=2$ のときだけ奇数次数の頂点が 2 個で条件を満たすが、$n\ge 4$ では奇数次数の頂点が $n\ge 4$ 個あり、条件を満たさない。

$3\le n\le 10$ で $n$ が奇数なのは $n=3,5,7,9$。偶数の $n=4,6,8,10$ は奇数次数の頂点がそれぞれ 4,6,8,10 個なので不可。

検算：$K_3$ は三角形で一周できる。$K_4$ は全頂点の次数が 3 で奇数頂点が 4 個あり不可能（ケーニヒスベルクの橋型）。

答え：$n=3,5,7,9$