📂グラフ理論

平面グラフの基本的性質

定理 ¹

$G$ が シンプル 平面グラフ だとしよう。

• [1]: $G$ が 連結グラフ で、$n \ge 3$ 個の頂点と $m$ 個のエッジを持つ場合、$m \le 3n - 6$
• [2]: すべてのシンプル平面グラフ $G$ は、$\deg v \le 5$ の頂点 $v \in V(G)$ を少なくとも一つ持つ。

証明

[1]

平面グラフの各面は少なくとも三つのエッジに囲まれているとする。

最も簡単なケースとして、完全グラフ $K_{3}$ がただ一つ存在し、エッジ $m=3$ と面 $f=2$ の場合、もう一つ面を追加するためには少なくとも二つのエッジが必要であるため、$3f \le 2m$ となる。

オイラーの公式: 連結平面グラフ $G$ について、$n:=|V(G)|$, $m:=|E(G)|$, そして $f$ を面の数とすると $$ n-m+f=2 $$

オイラーの公式に従い、$f = m - n + 2$ なので $$ 3(m-n+2) \le 2m $$ これにより $m \le 3n - 6$ を得る。

■

[2]

$G$ は連結である必要はないが、各コンポーネントをチェックするだけで十分だ。一般性を失わずに $G$ が連結グラフで、少なくとも $3$ 個の頂点を持つとしよう。背理法を使うために $G$ の全ての頂点の次数が $6$ 以上であると仮定する。

$G$ の頂点数が $n \ge 3$ で、エッジ数が $m$ の場合、全ての頂点の次数が $6$ 以上であるため $$ 6n \le 2m $$ 両辺を $2$ で割ると $3n \le m$ になるが、要約 [1] によると $$ 3n \le 3n - 6 $$ これは矛盾であるため、$\deg v \le 5$ の頂点 $v \in V(G)$ が少なくとも一つ存在しなければならない。

■