13.4 平面グラフの辺数の上界
Euler の公式と同様に、定義 13.2.2 から構造的帰納法を使って簡単に示せる補題がいくつかある:
補題 13.4.1
任意の連結グラフの平面埋め込みにおいて、それぞれの辺は異なる二つの離散面に一度ずつ含まれるか、一つの離散面にちょうど二度含まれるかのいずれかである。
補題 13.4.2
\(3\) 個以上の頂点を持つ任意の連結グラフの平面埋め込みにおいて、任意の離散面の長さは \(3\) 以上である。
補題 13.4.1 と補題 13.4.2 と Euler の公式を使うと、平面グラフの辺の個数には上界があることが示せる:
定理 13.4.3
連結平面グラフ が \(v \geq 3\) 個の頂点と \(e\) 個の辺を持つなら、次の不等式が成り立つ:
\[ e \leq 3v - 6 \tag{13.3}\]
証明 定義より、連結なグラフが平面なのは平面埋め込みを持つとき、かつそのときに限る。そこで \(v \geq 3\) 個の頂点と \(e\) 個の辺を持つ連結なグラフが \(f\) 個の離散面からなる平面埋め込みを持つとする。補題 13.4.1 より、\(e\) 個の辺はそれぞれ離散面にちょうど二度含まれる。よって離散面の長さの和は \(2e\) に等しい。さらに補題 13.4.2 より \(v \geq 3\) なら全ての離散面の長さが \(3\) 以上なので、離散面の長さの和が \(3f\) 以上だと分かる。この二つの事実から次の不等式を得る:
\[ 3f \leq 2e \tag{13.4}\]
Euler の公式より \(f = e - v + 2\) が成り立つので、不等式 \(\text{(13.4)}\) の \(f\) に代入すれば次の関係を得る:
\[ \begin{aligned} 3(e - v + 2) &\leq 2e \\ e - 3v + 6 &\leq 0 \\ e &\leq 3v - 6 \end{aligned} \]
■