平面グラフとオイラーの公式

連結な平面グラフで $n - e + f = 2$ と「面の長さの和 $= 2 e$ 」を使い、面の数を求められる。また $e \leq 3 n - 6$ （2 部グラフなら $e \leq 2 n - 4$ ）を導いて、 $K_{5}$ , $K_{3, 3}$ などが平面的でないことを示せる

前提

2 部グラフと奇閉路（大学数学グラフ理論）

この技能までの道筋（7 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）
2 部グラフと奇閉路（大学数学グラフ理論）

説明

交差なしに平面に描いたグラフでは、頂点数 $n$ ・辺数 $e$ ・面の数 $f$ の間に $n - e + f = 2$ という関係が成り立ちます。これを使うと、絵を描かずに面の数を計算できます。さらに「面の長さの和 $= 2 e$ 」と組み合わせると、平面に描けるグラフの辺の数に上限 $e \leq 3 n - 6$ が得られます。この上限を超えるグラフは平面に描けないとわかるので、 $K_{5}$ や $K_{3, 3}$ が平面的でないことを示せます。

なぜそうしてよいのか

辺どうしが交わらないように平面に描いたグラフを平面グラフといい、そのように描けるグラフを平面的といいます。描いた線（頂点と辺）を平面から取り除くと、平面はいくつかの領域に分かれます。この領域を面と呼びます。いちばん外側の果てしなく広がる領域（外面）も 1 つの面として数えます。連結な平面グラフは、1 頂点だけの状態から、すでに描いた部分が連結なまま辺を 1 本ずつ描き足して作れます。最初は $n = 1, e = 0, f = 1$ なので $n - e + f = 2$ です。描き足す辺には 2 種類あります。(ア) 新しい頂点へ伸ばす辺のときは、 $n$ と $e$ が 1 ずつ増え、面は分かれません。(イ) すでにある 2 頂点を結ぶ辺のときは、その辺がある面を 2 つに仕切るので、 $e$ と $f$ が 1 ずつ増えます。どちらの場合も $n - e + f$ は変わらないので、最後まで $n - e + f = 2$ が保たれます。

面の長さとは、その面の境界を一周したときにたどる辺の本数です。両側が同じ面になっている辺（橋のような辺）は、一周するあいだに 2 回通るので 2 と数えます。どの辺も、両側の面の境界で合わせてちょうど 2 回数えられます。したがって、すべての面の長さの和は $2 e$ です。これは、次数の和が $2 e$ になる握手補題の「面版」にあたります。

単純グラフ（ループや多重辺がないグラフ）で $n \geq 3$ のとき、面の境界を一周する道の長さは 1 や 2 にはなれません。そのため各面の長さは 3 以上で、 $2 e \geq 3 f$ となります。これを $f = 2 - n + e$ に代入すると、 $2 e \geq 3 (2 - n + e)$ より $e \leq 3 n - 6$ が得られます。2 部グラフの場合は、奇数長の閉路をもたないので、境界を一周する道の長さは偶数です。それが 2 になることもないので、各面の長さは 4 以上です。 $2 e \geq 4 f$ から同様に計算して $e \leq 2 n - 4$ が得られます。

手順

グラフが連結であることと、交差なしに描かれている（平面グラフである）ことを確かめる。
頂点数 $n$ と辺数 $e$ を求める。次数が与えられているときは、握手補題 $\sum de g v = 2 e$ から $e$ を出す。
オイラーの公式 $n - e + f = 2$ から面の数を求める： $f = 2 - n + e$ （外面も 1 つと数えた個数）。
面の長さの情報があるときは、その和が $2 e$ になることを使って、未知の量を決めたり計算を検算したりする。
平面的でないことを示すときは、平面的だと仮定する。単純で $n \geq 3$ なら $e \leq 3 n - 6$ 、さらに 2 部グラフなら $e \leq 2 n - 4$ が成り立つはずなので、実際の $e$ がこれを破ることを確かめて矛盾を導く。例： $K_{5}$ は $e = 10 > 3 \cdot 5 - 6 = 9$ 、 $K_{3, 3}$ は $e = 9 > 2 \cdot 6 - 4 = 8$ 。

例題

連結な単純平面グラフ $G$ があり、頂点数は $10$ 、どの頂点の次数も $3$ である。 $G$ の面の数（外面も含む）を求めよ。

例題の解答

手順 1： $G$ は連結な平面グラフなので、オイラーの公式が使えます。
手順 2：握手補題より $2 e = \sum de g v = 3 \times 10 = 30$ なので、 $e = 15$ です。頂点数は $n = 10$ です。
手順 3： $f = 2 - n + e = 2 - 10 + 15 = 7$ です。
手順 4（検算）：面は 7 個で、長さの和は $2 e = 30$ になるはずです。各面の長さは 3 以上なので和は $3 \times 7 = 21$ 以上となり、矛盾はありません。また $e = 15 \leq 3 \cdot 10 - 6 = 24$ も満たしています。
よって面の数は $7$ です。

答え: $7$

よくある誤り

外面（外側の無限に広がる領域）を数え忘れて、 $f$ を 1 小さくしてしまう誤り。正しくは外面も 1 つの面として数え、例えば三角形 $C_{3}$ は内側と外側で $f = 2$ となり、 $3 - 3 + 2 = 2$ が成り立つ。
連結でないグラフにも $n - e + f = 2$ を使ってしまう誤り。正しくは連結成分が $c$ 個なら $n - e + f = 1 + c$ となる。例えば辺のない 2 頂点では $n = 2, e = 0, f = 1$ なので $n - e + f = 3$ である。
面の長さの和を $e$ としてしまう誤り。正しくは各辺が 2 回数えられるので和は $2 e$ 。両側が同じ面である辺は、その面の長さに 2 と数える。例えば 3 頂点の道 $P_{3}$ は面が 1 つで、その長さは $4 = 2 \cdot 2$ である。
$e \leq 3 n - 6$ を満たせば平面的だと結論してしまう誤り。この不等式は平面的であるための必要条件にすぎない。例えば $K_{3, 3}$ は $9 \leq 3 \cdot 6 - 6 = 12$ を満たすが平面的でない。この場合は 2 部グラフ用の $e \leq 2 n - 4$ を使い、 $9 > 8$ から矛盾を導く必要がある。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

ガウス・ボンネの定理（大域版）とオイラー標数（大学院数学微分幾何）