グラフ理論の問題

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

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

$G$ は頂点が $12$ 個の連結な単純平面グラフである。$G$ を平面上に辺が交差しないように描いたところ、すべての面（外側の非有界な面も含む）の境界がちょうど $3$ 本の辺からなる閉路（三角形）になった。この描き方における $G$ の面の数 $f$ を求めよ。

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

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

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

連結な単純グラフ $G$ が、辺どうしが交わらないように平面上に描かれている（平面グラフ）。$G$ の頂点数は $10$ で、どの頂点の次数もちょうど $3$ である。この描画で平面が辺によって分けられる面の数 $f$ を求めよ。ただし、外側の有界でない領域も $1$ つの面として数える。