はむ。日記

離散数学とか解析学とかアニメについてつぶやきます。

オイラーの公式の応用

グラフ理論

[Def]平面グラフ

グラフが平面グラフであるとは、辺が交わることなく平面(または2次元球面)上に描くことができるグラフのことである。

■オイラーの公式■

Gが連結平面グラフで、 $n$ 個の頂点、 $e$ 個の辺、 $f$ 個の面を持てば、次の関係式が成り立つ。

${\displaystyle\ n - e + f = 2}$

[離散幾何でしばしば使われる命題]

Gを空でない単純(多重辺とループがない)連結平面グラフとする。このとき以下が成り立つ。

(1) Gは高々5次の頂点を持つ。

(2)Gの辺の数は高々 $3n-6$ である。

(記号の注意)

$k$ 面とは $k$ 個の辺で囲まれた面のこととする。

$f_{k}$ を $k$ 面の数とする。

$n_{i}$ をグラフGにおける次数 $i$ の頂点の数とする。

(証明)

Gの頂点数を $n$ ,辺数を $e$ ,面数を $f$ とする。

Gは単純グラフだから、あらゆる面は少なくとも3つの辺を持つ。

$f = f_{3} + f_{4} + f_{5} +.....$

$2e = 3f_{3} + 4f_{4} + 5f_{5} + ....$

が得られ、 $2e - 3f ≧0$ となる。

ここで、もし全ての頂点の次数が少なくとも6であれば

$n = n_{6} + n_{7} + n_{8} + ...$

$2e = 6n_{6} + 7n_{7} + 8n_{8} + ...$

が得られ、 $2e - 6n ≧0$ となる。

2つの不等式をあわせると、

$6(e - n - f) = (2e - 6n) + 2(2e - 3f) ≧0$

つまり $e ≧ n +f$ が得られるが、これはオイラーの公式に矛盾する。■

(2)　(1)より $2e - 3f ≧0$ が得られていたので、オイラーの公式から

$3n - 6 = 3e - 3f ≧ e$ となる。■