# オイラーの公式 ## 定義 オイラーの公式(Euler's Formula、Theorem 12.3.1)は、連結な平面グラフが平面埋め込みを持つとき、頂点数 v・辺数 e・面数 f の間に v − e + f = 2 という関係が常に成り立つという定理である。ここでの「面」は、平面埋め込みの離散な面(discrete face、境界を閉歩道として捉えたもの)を指し、外側に無限に広がる面も1つの面として数える。証明は平面埋め込みの再帰的定義(基底部: 単一頂点、構成子: 面を分割する/橋を追加する)に対する構造的帰納法で行う。基底部の単一頂点グラフでは v=1, e=0, f=1 で 1−0+1=2。「面を分割する」構成子は辺を1本・面を1つ増やすだけなので v−e+f は不変。「橋を追加する」構成子は2つの独立な埋め込みを1本の橋で結び、頂点数・辺数はそれぞれの和(辺は橋の分+1)になる一方、併合される2つの面が1つの面になるため面数は和から1減り、(v_G+v_H)−(e_G+e_H+1)+(f_G+f_H−1) は帰納法の仮定により (v_G−e_G+f_G)+(v_H−e_H+f_H)−2 = 2+2−2 = 2 と計算できる。両方の構成子で v−e+f=2 という不変条件が保たれるため、すべての平面埋め込みで成立する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.3) オイラーの公式は本章のその後の結果すべての基盤になる。各辺が面の境界にちょうど2回出現すること(Lemma 12.4.1)と、v≥3のとき各面の境界長が3以上であること(Lemma 12.4.2)を組み合わせて 3f≤2e を導き、これにオイラーの公式 f=e−v+2 を代入すると平面グラフの辺数の上界 e≤3v−6 が得られる(二部グラフでは境界長が4以上になり e≤2v−4)。この上界から K5・K3,3 の非平面性、平面グラフが常に次数5以下の頂点を持つこと(5-彩色定理の鍵となる補題)が従う。正多面体の分類では、各頂点にm個の面が集まり各面がn辺を持つという関係式 mv=2e, nf=2e をオイラーの公式に代入して 1/m+1/n=1/e+1/2 を導き、この式を満たす(n,m)の組が5通りしかないことから正多面体が5種類に限られることを示す。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.4, §12.7) ## 横断的知見 - オイラーの公式の証明は、第6章で確立された構造的帰納法(再帰的データ型の基底部・構成子部それぞれで性質の成立を示す証明技法)を、平面埋め込みという新しい再帰的データ型に適用した具体例になっている。第6章時点では文字列・算術式・木構造といった記号的なデータ型が主な適用対象だったが、第12章は「面の集合」という幾何学的な対象を離散データ型として再定義したうえで同じ証明技法を適用しており、構造的帰納法が記号操作に限らず連続幾何学の代替物としても機能することを具体的に示す事例である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 6 Recursive Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.3) - 第11章の握手補題(次数の総和=辺数の2倍)は「頂点の次数」という局所的な量に関する恒等式だったのに対し、オイラーの公式は「頂点・辺・面」という3種類の大域的な量の間の恒等式であり、両者は第12章§12.6で組み合わされて使われる(次数の総和が2eであることと e≤3v−6 の組み合わせから、平面グラフには次数5以下の頂点が必ず存在するという Lemma 12.6.3 が導かれる)。この結合は、単純グラフの局所的な数え上げ論法(次数)と平面グラフの大域的な数え上げ論法(面)が独立ではなく、握手補題を経由して1本の証明の中で連鎖することを示している。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]], [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.6) ## 未解決の問い - オイラーの公式は非連結グラフには v−e+f=2 の形では成り立たず、連結成分数 c を使った v−e+f−2c=0 に一般化される(章末の演習12.4で示唆されるのみで、本文中には証明がない)。この一般化の構造的帰納法による証明は本章単独からは追えない。 - オイラーの公式は球面上の埋め込みについて成り立つことが直感的に説明されるが、種数(genus)がより高い曲面(トーラスなど)への一般化(v−e+f=2−2g)は本章では触れられていない。 ## 関連 - 概念: [[平面グラフ]] / [[単純グラフ]] / [[帰納法]] / [[グラフ彩色]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 12.