グラフ理論の問題

頂点集合 $V=\{s,a_1,a_2,a_3,a_4,b_1,b_2,b_3\}$ と、次の $10$ 本の辺からなる単純無向グラフ $G$ を考える。
$$E=\{s{a}_1,a_1{a}_2,a_2{a}_3,a_3{a}_4,a_{4}s,a_1{a}_3,s{b}_1,b_1{b}_2,b_2{b}_3,b_{3}s\}$$
$G$ で隣接していない相異なる $2$ 頂点の組 $\{u,v\}$ に対し、$G$ に辺 $uv$ を $1$ 本加えた単純グラフを $G+uv$ と書く。

ここで、オイラー路とはすべての辺をちょうど $1$ 回ずつ通る道（始点と終点は一致してもしなくてもよい）であり、ハミルトン閉路とはすべての頂点をちょうど $1$ 回ずつ通る閉路である。

隣接していない $2$ 頂点の組 $\{u,v\}$ のうち、
- $G+uv$ がオイラー路をもつものの個数を $p$、
- $G+uv$ がハミルトン閉路をもつものの個数を $q$、
- $G+uv$ がオイラー路とハミルトン閉路の両方をもつものの個数を $r$

とする。組 $(p,q,r)$ をこの順に求めよ。

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

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

整数 $n$ は $2\le n\le 10$ を満たすとする。$n$ 個の頂点からなる完全グラフ $K_n$（相異なる 2 頂点がすべてちょうど 1 本の辺で結ばれた単純無向グラフ）を考える。

ここで、オイラー閉路とは、グラフのすべての辺をちょうど 1 回ずつ通り、出発した頂点に戻ってくる道のことである（同じ頂点は何度通ってもよい）。

$K_n$ がオイラー閉路をもつような $n$ をすべて求めよ。

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

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

頂点集合を $V=\{1,2,3,\dots ,12\}$ とし、相異なる 2 頂点 $i,j$ を、一方が他方を割り切るときに限り辺で結んだ単純無向グラフを $G$ とする（たとえば $\{2,6\}$ は辺であり、$\{4,6\}$ は辺ではない）。

$G$ のすべての辺を、どの 2 本の道も辺を共有しないような何本かの道に分ける。各辺はちょうど 1 本の道に含まれるようにする。ここで「道」とは、同じ辺を 2 度通らない歩道のことである。頂点は何度通ってもよく、始点と終点は一致してもしなくてもよい。

このように分けるとき、必要な道の本数の最小値を求めよ。