13.3 Euler の公式

平面埋め込みの再帰的定義の価値は、平面グラフに関する性質の証明で強力なテクニックが利用可能になる点にある。つまり再帰的定義があれば構造的帰納法が可能になる。例えば、定義 13.2.2 と構造的帰納法を使えば連結平面グラフが持つ最も基礎的な性質を証明できる: グラフの全ての平面埋め込みにおいて、頂点の個数と辺の個数は離散面の個数を完全に決定する:

例えば図 \(\text{13.5}\) では \(v = 4\), \(e = 6\), \(f = 4\) であり、確かに \(4 - 6 + 4 = 2\) が成り立っている。

証明 平面埋め込みの定義に関する構造的帰納法で示す。述語 \(P(\mathcal{E})\) を「平面埋め込み \(\mathcal{E}\) で \(v - e + f = 2\) が成り立つ」と定める。

ベースケース: \(\mathcal{E}\) が単一の頂点からなる長さ \(0\) の閉路だけを含む単元集合のとき、\(v = 1\), \(e = 0\), \(f = 1\) より \(v - e + f = 1 - 0 + 1 = 2\) なので \(P(\mathcal{E})\) は成り立つ。

構築ケース: [面の分割] 平面埋め込みを持つ連結グラフを \(G\) とする。その平面埋め込みに属する離散面 \(\gamma\) と、\(\gamma\) に属する隣接しない異なる二頂点 \(a\), \(b\) を取る。

このとき、\(G\) の辺集合に辺 \(\langle a\>\text{---}\>b \rangle\) を加えて得られるグラフは \(G\) より辺の個数が \(1\) だけ多く、かつ離散面の個数が \(\mathcal{E}\) より \(1\) だけ多い平面埋め込みを持つ。よって二つのグラフは同じ \(v - e + f\) の値を持つ。構造的帰納法の仮定より \(G\) では \(v - e + f\) の値が \(2\) なので、\(G\) に辺 \(\langle a\>\text{---}\>b \rangle\) を加えたグラフでも \(2\) である。よって、このケースで新しく構築される平面埋め込みでも \(P\) は成り立つ。

構築ケース: [橋の追加] \(G\) と \(H\) が連結なグラフで、頂点集合が共通部分を持たず、それぞれ平面埋め込みを持つと仮定する。このとき二つのグラフを橋で結ぶと \(2\) 個の離散面が除去されて \(1\) 個の新しい離散面が加わり、他の離散面は影響を受けない。よって橋を追加する操作の結果として得られるグラフは \(v_{G} + v_{H}\) 個の頂点と \(e_{G} + e_{H} + 1\) 個の辺を持ち、\(f_{G} + f_{H} - 1\) 個の離散面からなる平面埋め込みを持つ。よって次の等式を得る:

つまり構築された新しいグラフでも \(v - e + f = 2\) が成り立つ。よって、このケースでも \(P(\mathcal{E})\) は成り立つ。

以上で構築ケースの証明が完了したので、構造的帰納法の原理より定理は成り立つ。 ■