グラフ理論の問題

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

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

$G$ を頂点数 $n$、辺数 $e$ の連結な単純グラフとし、$G$ は平面に辺が交差しないように描かれている（平面グラフ）とする。この描画で平面が分けられてできる領域（外側の非有界な領域も含む）を面といい、その個数を $f$ とする。各面について、その境界をたどる閉路状の歩道の長さ（境界上の辺のうち、両側がともにその面であるものは 2 回数える）をその面の長さという。

$G$ のすべての頂点の次数が $3$ 以上であるとき、$G$ には長さが $5$ 以下の面が少なくとも 1 つ存在することを証明せよ。

なお、連結な平面グラフに対するオイラーの公式 $n-e+f=2$ と、すべての面の長さの和が $2e$ に等しいことは用いてよい。

$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$ の辺の数を求めよ。