グラフ理論の問題

整数 $n$ は $3\le n\le 10$ を満たすとする。$K_n$ を $n$ 個の頂点からなる完全グラフ（単純無向グラフで、相異なるどの 2 頂点も辺で結ばれているもの）とする。

$K_n$ が一筆書きできる、すなわち「辺をたどって進む経路で、$K_n$ のすべての辺をちょうど 1 回ずつ通るもの」をもつような $n$ をすべて求めよ。ただし、この経路では同じ頂点は何度通ってもよく、始点と終点は一致してもしなくてもよい（このような経路をオイラー路という）。

整数 $n$ は $2\le n\le 8$ を満たすとする。$n$ 頂点の完全グラフ $K_n$（単純無向グラフ。たとえば $K_2$ は $2$ 頂点を $1$ 本の辺で結んだグラフ）が一筆書きできるような $n$ をすべて求めよ。

ここで「一筆書きできる」とは、ある頂点から出発して辺をたどり、すべての辺をちょうど $1$ 回ずつ通る経路が存在することをいう。この経路では、同じ頂点は何度通ってもよい。同じ辺を $2$ 回以上通ってはいけない。出発点と終点は一致してもしなくてもよい。

整数 $m,n$ は $2\le m\le n\le 6$ を満たすとする。完全 2 部グラフ $K_{m,n}$（単純グラフ）が「オイラー閉路をもつ」または「ハミルトン閉路をもつ」の少なくとも一方を満たすような組 $(m,n)$ の個数を求めよ。

ここで、オイラー閉路とはすべての辺をちょうど 1 回ずつ通って出発点に戻る閉じた道のことであり、ハミルトン閉路とはすべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路のことである。

正の整数 $m,n$ に対し、$K_{m,n}$ を、$m$ 個の頂点からなる部集合と $n$ 個の頂点からなる部集合をもつ完全二部グラフとする。

ここでは、グラフのすべての辺をちょうど 1 回ずつ通る道（始点と終点は一致してもしなくてもよい）をオイラー路とよぶ。

$1\le m\le n\le 6$ をみたす整数の組 $(m,n)$ のうち、$K_{m,n}$ がオイラー路をもつものは何組あるか。

$9$ 個の頂点からなる完全グラフを $K_9$ とする。$K_9$ は、相異なる $2$ 頂点がどれもちょうど $1$ 本の辺で結ばれている単純無向グラフである。各頂点の次数と握手補題 $\sum _{v\in V}\mathrm{deg}v=2|E|$ を用いて、$K_9$ の辺の本数 $|E|$ を求めよ（答えるのは辺の本数 $|E|$ だけでよい）。