グラフ理論の問題

正二十面体の頂点と辺を、そのまま頂点と辺とする単純無向グラフ $G$（正二十面体グラフ）を考える。$G$ の頂点は $12$ 個である。正二十面体の各頂点には $5$ 本の辺が集まっているので、$G$ のどの頂点の次数も $5$ である。握手補題を用いて、$G$ の辺の数を求めよ。

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

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

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

頂点が $10$ 個の単純無向グラフ $G$ があり、次数が $3$ の頂点がちょうど $4$ 個、次数が $4$ の頂点がちょうど $6$ 個ある（これで $10$ 個の頂点すべてである）。$G$ の辺の本数を求めよ。

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

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

頂点集合を $V=\{1,2,3,4,5\}$ とし、辺集合 $E$ を次の $9$ 本の辺からなるものとする単純無向グラフ $G=(V,E)$ を考える（$G$ は完全グラフ $K_5$ から辺 $\{4,5\}$ を除いたグラフである）。
$$\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\}$$
$G$ の辺彩色数 ${\chi }^{\prime }(G)$ を求めよ。ただし、辺彩色とは、共通の端点をもつ 2 本の辺が異なる色になるように各辺に色を塗ることであり、辺彩色数とはそれに必要な色の数の最小値である。