グラフ理論の問題

頂点の数を $n$、辺の数を $e$、面の数を $f$ とします。$n=12$ です。

手順 1：面の長さの和を辺の数で表す

面の境界をたどったときに通る辺の本数（同じ辺を $2$ 回通ればそれも $2$ 本と数える）を、その面の長さといいます。一般の連結な平面グラフでは、橋でない辺は異なる $2$ つの面の境界に $1$ 回ずつ現れ、橋は同じ $1$ つの面の境界に $2$ 回現れます。どちらの場合も、各辺は面の長さの和にちょうど $2$ 回数えられるので
$$\sum _{\text{面}}(\text{面の長さ})=2e$$
が成り立ちます。

なお、この問題のグラフには橋がありません。どの辺も少なくとも $1$ つの面の境界に含まれ、すべての面の境界は三角形の閉路なので、どの辺も閉路の上にあります。閉路上の辺を取り除いても、閉路の残りの $2$ 辺を通って両端の頂点は結ばれたままなので、その辺は橋ではありません。したがって、この問題では各辺はちょうど $2$ つの異なる面の境界に $1$ 回ずつ現れます。

すべての面の長さが $3$ なので、左辺は $3f$ です。よって
$$3f=2e\text{すなわち}e=\frac{3}{2}f.(1)$$

手順 2：オイラーの公式を使う

$G$ は連結な平面グラフなので、オイラーの公式
$$n-e+f=2(2)$$
が成り立ちます。

手順 3：連立して解く

$(2)$ に $n=12$ と $(1)$ を代入すると
$$12-\frac{3}{2}f+f=2$$
$$12-\frac{1}{2}f=2$$
$$\frac{1}{2}f=10$$
$$f=20.$$

このとき $e=\frac{3}{2}\times 20=30$ で、$n-e+f=12-30+20=2$ となり確かに成り立ちます（正二十面体の頂点と辺がつくるグラフがこの例です）。

したがって、面の数は $20$ です。

頂点数 $v=12$、辺数 $e$、面数 $f$ とする。連結な平面グラフなのでオイラーの公式 $v-e+f=2$ が成り立つ。

すべての面の境界が長さ 3 の閉路であり、各辺は（橋でない限り）ちょうど 2 つの面の境界に現れる。よって面の境界の長さの総和は $3f=2e$ である。

このグラフに橋があるとすると、橋は同じ面に 2 回現れ、その面の境界は 3 本の辺からなる閉路ではなくなる。したがって橋はなく、各辺は異なる 2 つの面の境界に 1 回ずつ現れる。

$e=\frac{3f}{2}$ をオイラーの公式に代入すると $12-\frac{3f}{2}+f=2$ となる。これより $\frac{f}{2}=10$、すなわち $f=20$ を得る。このとき $e=30$ である。

検算：$12-30+20=2$ で成り立つ。また $3\cdot 20=60=2\cdot 30$ で成り立つ。正二十面体グラフ（頂点 12、辺 30、面 20）がこの条件を満たす例になっている。

したがって $f=20$ である。