グラフ理論の問題

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

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

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

次の 4 つの単純無向グラフ $G_1,G_2,G_3,G_4$ を考える。

• $G_1$：完全 2 部グラフ $K_{3,3}$
• $G_2$：完全 2 部グラフ $K_{2,3}$
• $G_3$：頂点集合 $\{1,2,3,4,5\}$、辺集合 $\{12,13,23,34,35,45\}$
• $G_4$：頂点集合 $\{1,2,3,4,5,6\}$、辺集合 $\{14,13,25,26,36,45,23\}$

ここで辺 $ij$ は頂点 $i$ と頂点 $j$ を結ぶ辺を表す。ハミルトン閉路（すべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路）をもつグラフ $G_i$ の番号 $i$ の集合を求めよ。

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

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

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

次の $5$ つの単純無向グラフ $G_1,G_2,G_3,G_4,G_5$ のうち、ハミルトン閉路（すべての頂点をちょうど $1$ 回ずつ通って出発点に戻る閉路）をもつものの番号をすべて求め、集合で答えよ。

• $G_1$：完全 2 部グラフ $K_{2,3}$
• $G_2$：完全 2 部グラフ $K_{3,3}$
• $G_3$：頂点集合 $\{1,2,3,4,5\}$、辺集合 $\{12,13,23,34,35,45\}$
• $G_4$：頂点集合 $\{1,2,3,4,5,6\}$、辺集合 $\{12,13,24,34,35,46,56\}$
• $G_5$：頂点集合 $\{1,2,3,4,5,6,7\}$、辺集合 $\{12,14,23,34,45,56,67,72\}$

ただし、辺 $ij$ は頂点 $i$ と頂点 $j$ を結ぶ辺を表す。

頂点集合 $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)$ をこの順に求めよ。