組合せとグラフの理論（塩田）第9回 (3)　オイラーの公式
前へ / 戻る / 次へ

「面」の定義

　平面グラフに「面」を定義するために、ひとつ定理を書きます。
Th.14　グラフが平面上に辺の交差無く描けることと、 球面上に辺の交差無く描けることは同値である。
証明　$\Rightarrow$ )　小さな紙に描いておいて球面に張り付ければよい。
　→　
$\Leftarrow$ )　グラフを避けて球面に穴をあけて、穴を広げればよい。
　→　
(証明終)
Rem.15　
  • Th9-10 の証明は、球面上に描くと思えば内側外側の区別が不要になります。
  • プラトングラフの平面グラフとしての描画 ( Ex.5 ) は、正多面体の面のひとつに穴をあけて広げたものです。
Def.16　平面グラフの、辺で区切られた各領域を「面」と呼ぶ。 一番外側も 1 つの面と考える。
※　球面上に描けば「一番外側」という区別がなくなるので、その面も同等に扱う訳です。
※ 「面」と言うときは 辺が交差していないことが前提 です。 ここ特に大事！！

オイラーの公式

Th.17（オイラーの公式）　$G$ を連結な平面グラフ、$n$, $m$, $f$ をその頂点数、辺数、面の個数とする。 このとき
$n - m + f = 2$
が成り立つ。
Ex.18　プラトングラフで確かめてみましょう。
Th.17 の証明　$m$ についての帰納法を用います。
  1. $m$ が一番少ないのは $G$ が木のときで $m=n-1$ であり、面は外側のひとつだけなので $f=1$。 よって $n-m+f = n - (n-1) + 1= 2$ となって成り立ちます。
  2. $G$ が木でないときは、$G$ 内の閉路 $C$ と、$C$ 上の辺 $e$ を 1 本選んで
    $G'=G-e$
    を考えます。$G'$ は $G$ の部分グラフゆえ平面グラフで、そのパラメータを $n'$, $m'$, $f'$ とおくと
    • 頂点は消していないので $n'=n$
    • 辺は 1 本除去したので $m'=m-1$
    • $e$ の表側の 2 つの面が 1 つにつながったので $f'=f-1$
    よって
    $n-m+f=n'-(m'+1)+(f'+1)=n'-m'+f'=2$.
    ここで $G'$ に帰納法の仮定を使いました。(証明終)

平面的グラフは辺が少ない

Cor.19　$G$ を連結な平面的単純グラフ、$n$, $m$ をその頂点数、辺数とする。 このとき次が成り立つ。
  1. $m \leqq 3n-6$.
  2. $G$ が3角形を含まなければ $m \leqq 2n-4$.
  3. 次数 5 以下の頂点が必ずある。
証明　(1)　1 つの面は 3 本以上の辺で囲まれていて、1 本の辺は 2 つの面で使われますので、
$3f \leq 2m$
が成り立ちます。従って
$2=n-m+f \leqq n -m + \frac{2}{3}m = n- \frac{1}{3}m$.
(2)　3角形を含まなければ 1 つの面は 4 本以上の辺で囲まれますので、今度は
$4f \leq 2m$
となり
$2=n-m+f \leqq n -m + \frac{1}{2}m = n- \frac{1}{2}m$.
(3)　もし全ての頂点の次数が 6 以上であれば
$2m=$ 次数の和 $\geqq 6n$
となって (1) に矛盾します。 (証明終)

※　プリントの「第3の証明」はこの Cor.19 と同じパターンを使ったものです。

辺が少ないからと言って平面的グラフとは言えない

※　Cor.19 の条件は必要条件でしかなく、 $m \leqq 3n - 6$ が成り立ったからと言って平面的であるとは言えません。 ここも大事！

$n=100$, $m=105$ なので $m \leqq 3n -6$ は成り立つが非平面的な例 ( $K_5$ を含むので非平面的 )

前へ / 戻る / 次へ