平面グラフのオイラーの公式

基底段階。$E$ $= 0$ でグラフが連結であれば、それは単一の頂点のみからなり($V=1$)、面はちょうど一つ、非有界な平面全体である($F=1$)。このとき $1 - 0 + 1 = 2$ が成り立つ。

帰納段階、場合1:サイクル上にある辺。公式が $E$ より少ない辺を持つすべての連結平面グラフで成り立つと仮定し、グラフが $E$ $\ge 1$ 本の辺を持つとする。ある辺 $e$ がサイクル上にあれば、$e$ を除いてもグラフは連結のままである(サイクルの残りの部分がその両端点をまだつないでいる)。$e$ を除くとその両側の2つの面が一つの面に統合されるので、より小さいグラフは $V$ 個の頂点、$E - 1$ 本の辺、$F - 1$ 個の面を持つ。帰納法の仮定より $V - (E-1) + (F-1) = 2$ であり、これは $V - E + F = 2$ に簡単化される。

帰納段階、場合2:どの辺もサイクル上にない。このときすべての辺が橋であり、グラフには全くサイクルがない、すなわち木である。平面上に描かれた木はちょうど一つの面を持ち($F = 1$、唯一の非有界な領域。閉じ込めるべき有界な領域を作るサイクルがないため)、木に関する標準的な事実として、$V$ 頂点の木はちょうど $E = V - 1$ 本の辺を持つ。代入すると $V - E + F = V - (V - 1) + 1 = 2$ となる。

結論。すべての場合が公式の成立に帰着するか、(一辺を除くことで)帰納法によって成り立つより小さいグラフに帰着するので、任意の連結な平面グラフについて $V - E + F = 2$ が成り立つ。