グラフ理論の問題

判定に使う定理

一筆書きの経路は、辺の重複を許さず頂点の重複を許す経路で、すべての辺を通るものである。これはオイラー路（始点と終点が一致するときはオイラー閉路）とよばれる。連結グラフについて、次の定理が成り立つ。
- オイラー閉路をもつ $⟺$ すべての頂点の次数が偶数
- オイラー路（始点と終点が一致しなくてもよい）をもつ $⟺$ 奇数次の頂点が $0$ 個または $2$ 個

したがって、奇数次の頂点の個数が $0$ 個または $2$ 個かどうかを調べればよい。

手順1：連結性の確認

$K_n$ ($n\ge 2$) では任意の $2$ 頂点が辺で結ばれているので、$K_n$ は連結である。よって上の定理が使える。

手順2：次数を求める

$K_n$ の各頂点は、ほかの $n-1$ 個の頂点すべてと結ばれている。したがって、どの頂点の次数も $n-1$ である。

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

• $n$ が奇数のとき：$n-1$ は偶数なので、すべての頂点の次数が偶数である。奇数次の頂点は $0$ 個なので、オイラー閉路をもち、一筆書きできる。該当するのは $n=3,5,7$ である。たとえば $K_3$ は、頂点を $1\to 2\to 3\to 1$ とたどればよい。
• $n$ が偶数のとき：$n-1$ は奇数なので、$n$ 個の頂点がすべて奇数次である。奇数次の頂点は $n$ 個である。
• $n=2$ のとき：奇数次の頂点は $2$ 個なので、一筆書きできる。実際、$K_2$ はただ $1$ 本の辺からなり、その辺を $1$ 回通ればよい。
• $n=4,6,8$ のとき：奇数次の頂点は $4$ 個以上なので、一筆書きできない。

結論

条件を満たす $n$ は $2,3,5,7$ である。

$$\{2,3,5,7\}$$

$K_n$ は連結なので、一筆書き（オイラー路）ができる条件は、奇数次数の頂点の個数が $0$ または $2$ であること。
$K_n$ の各頂点の次数は $n-1$ である。

• $n$ が奇数のとき、$n-1$ は偶数で、奇数次数の頂点は $0$ 個。よって可能（オイラー閉路）。
• $n$ が偶数のとき、$n-1$ は奇数で、奇数次数の頂点は $n$ 個。$n=2$ のときだけ $2$ 個で可能。$n\ge 4$ では $4$ 個以上なので不可能。

$2\le n\le 8$ で確認する。
- $n=2$: 奇数次数の頂点は 2 個で可能。
- $n=3$: 全頂点の次数が 2 で可能。
- $n=4$: 全頂点の次数が 3 で、奇数次数の頂点は 4 個なので不可能。
- $n=5$: 全頂点の次数が 4 で可能。
- $n=6$: 全頂点の次数が 5 で、奇数次数の頂点は 6 個なので不可能。
- $n=7$: 全頂点の次数が 6 で可能。
- $n=8$: 全頂点の次数が 7 で、奇数次数の頂点は 8 個なので不可能。

したがって $n=2,3,5,7$。