グラフ理論の問題

$G$ を頂点数 $12$ の連結な単純グラフとし、$G$ のすべての頂点の次数は $5$ であるとする。$G$ は平面グラフであり、辺どうしが交差しないように平面上に描かれている。この描画における面の数 $f$ を求めよ。ただし、外側の非有界な面も $1$ つの面として数える。

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

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

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

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