平面グラフ メモ

平面グラフの性質についてのメモ　随時更新 vは頂点数, eは辺数, fは窓数 ここでfには、一番外側も含む

f = e - v + 2

非常に有名 証明は変数に関する数学的帰納法？

3f <= 2e

全部の多角形に接する辺の個数の和が2e(以下)であることと少なくとも一つの多角形は3個の辺に接することより

e <= 3v-6

上二つの式から出てくる。

f <= 2v-4

これも1つめと3つめの式から出てくる これにより、fはO(v)で抑えられる。