2015-06-23 平面グラフ メモ 平面グラフの性質についてのメモ 随時更新 vは頂点数, eは辺数, fは窓数 ここでfには、一番外側も含む f = e - v + 2 非常に有名 証明は変数に関する数学的帰納法? 3f <= 2e 全部の多角形に接する辺の個数の和が2e(以下)であることと少なくとも一つの多角形は3個の辺に接することより e <= 3v-6 上二つの式から出てくる。 f <= 2v-4 これも1つめと3つめの式から出てくる これにより、fはO(v)で抑えられる。