平面グラフ

辺数 $m$ に関する帰納法で示す。
基本段: $m=0$ のとき、$G$ が連結であることから頂点数は $n=1$ である。頂点も辺もない一点を平面に置いただけなので、平面には非有界な面が一つあるだけであり $f=1$。よって $n-m+f=1-0+1=2$。
帰納段: $m\geq1$ とし、辺数が $m-1$ 以下の連結平面グラフについて主張が成り立つと仮定する。
(i) $G$ が閉路を持たない場合、$G$ は木であり、次数1の頂点(葉)$v$ が存在する。$v$ に接続する唯一の辺を $e$ とし、$G':=G-v$($v$ と $e$ を取り除いたグラフ)とおくと、$G'$ は連結な平面グラフで頂点数 $n-1$、辺数 $m-1$ である。$e$ は $G$ の橋であり、その両側は同じ面に接していたから、$e$ と $v$ を取り除いても面の個数は変わらず $G'$ の面数も $f$ である。帰納法の仮定より $(n-1)-(m-1)+f=2$、これを整理すると $n-m+f=2$。
(ii) $G$ が閉路を持つ場合、閉路上の辺 $e$ を一つ選ぶ。$e$ は橋ではないので、$G':=G-e$(頂点は残し辺だけ取り除いたグラフ)は連結であり、頂点数 $n$、辺数 $m-1$ の平面グラフである。$e$ を取り除くと、$e$ を隔てとしていた二つの面が一つの面に合わさるので、$G'$ の面数は $f-1$ である。帰納法の仮定より $n-(m-1)+(f-1)=2$、これを整理すると $n-m+f=2$。
いずれの場合も主張が成り立つので、帰納法によりすべての連結平面グラフについて $n-m+f=2$ が成り立つ。

まず $G$ が連結な場合を示す。$G$ の一つの平面埋め込みを固定し、辺数を $m$、面数を $f$ とする。各面の境界を一周してもとに戻るまでにたどる辺の延べ本数を、その面の次数とよぶ(橋を境界に持つ面では、その橋を往復2回分として数える)。
$G$ が単純かつ $n\geq3$ なので、どの面の次数も3以上である。実際、次数1の面は自己ループを、次数2の面は(橋を挟まない限り)二重辺を要するが、単純グラフにはどちらも存在しない。各辺はちょうど二つの面の境界に現れる(橋の場合は同一の面に2回現れる)ので、全ての面の次数の総和は $2m$ に等しい。したがって
$$ 3f\leq\sum_{\text{面}}(\text{次数})=2m, $$
すなわち $f\leq\dfrac{2m}{3}$ を得る。これをEulerの公式 $n-m+f=2$ に代入すると
$$ 2=n-m+f\leq n-m+\frac{2m}{3}=n-\frac{m}{3}, $$
よって $\dfrac{m}{3}\leq n-2$、すなわち $m\leq3n-6$ が従う。
二部の場合は奇閉路を持たないので、各面の境界歩道の長さは偶数であり、単純性と $n\geq3$ から各面の次数は4以上になる。同様に $4f\leq2m$ を得て、Eulerの公式と合わせると $m\leq2n-4$ が従う。
最後に $G$ が非連結な場合を示す。$G$ の各連結成分から一頂点ずつ選び、外側の面を通して交差なく結ぶことで、頂点集合が $V(G)$ に等しい連結な単純平面グラフ $G'\supset G$ を作れる。$G$ が二部グラフの場合は、連結成分ごとに二部の名称を必要に応じて交換してから、異なる側の頂点どうしを結べば、$G'$ も二部グラフにできる。$n\geq3$ なので連結の場合の結果より $|E(G')|\leq3n-6$(二部の場合は $|E(G')|\leq2n-4$)であり、$E(G)\subset E(G')$ だから $|E(G)|\leq|E(G')|\leq3n-6$(二部の場合は $2n-4$)である。

$K_5$ は頂点数 $n=5$、辺数 $\binom{5}{2}=10$ の単純グラフである。もし $K_5$ が平面グラフならば、単純平面グラフの辺数の上界により
$$ 10=|E(K_5)|\leq3\cdot5-6=9 $$
でなければならないが、これは矛盾である。よって $K_5$ は平面グラフでない。

$K_{3,3}$ は頂点数 $n=6$、辺数 $3\cdot3=9$ の単純二部グラフである。$K_{3,3}$ は二部グラフだから三角形を持たない。もし $K_{3,3}$ が平面グラフならば、単純平面グラフの辺数の上界(二部の場合)により
$$ 9=|E(K_{3,3})|\leq2\cdot6-4=8 $$
でなければならないが、これは矛盾である。よって $K_{3,3}$ は平面グラフでない。

頂点数 $n\leq2$ なら明らかである。$n\geq3$ とし、辺数を $m$ とすると、上で証明した $m\leq3n-6$ と握手補題から
$$ \sum_{v\in V(G)}\deg(v)=2m\leq6n-12<6n. $$
したがって、すべての頂点の次数が $6$ 以上であることはできない。

辺数 $m$ に関する帰納法で示す。$m=0$ のとき、$G$ は $n$ 個の孤立点であり、$c=n$、$f=1$ だから $n-0+1=1+c$ である。
$m\ge1$ とし、辺数が $m-1$ の平面グラフ図について主張を仮定する。辺 $e$ を一つ選び、$G':=G-e$（頂点は残す）とおく。

• $e$ がある閉路の上にあるとき、$e$ を除いても連結成分の個数は $c$ のままで、$e$ を隔てとしていた二つの面が合わさるので $G'$ の面数は $f-1$ である。帰納法の仮定から $n-(m-1)+(f-1)=1+c$、すなわち $n-m+f=1+c$ である。
• $e$ がどの閉路の上にもないとき、$e$ は橋であり、$G'$ の連結成分は $c+1$ 個になり、面数は $f$ のままである。帰納法の仮定から $n-(m-1)+f=1+(c+1)$、すなわち $n-m+f=1+c$ である。

平面埋め込みを一つ固定し、面の数を $f$、連結成分の個数を $c$ とする。
各面の境界は閉路を含む。面 $F$ の境界 $\partial F$ は $G$ の頂点と辺からなる部分グラフである。もし $\partial F$ が閉路を含まなければ、$\partial F$ は森である。森の平面グラフ図の補集合 $\mathbb R^2\setminus\partial F$ は、上に述べたとおり連結である。$F$ は開集合であり、$\partial F$ の外では閉集合でもあるので、$F=\mathbb R^2\setminus\partial F$ となる。ところが $G$ は閉路をもち、その閉路のある辺 $e$ は森 $\partial F$ に含まれない。$e$ の内部の点は $\mathbb R^2\setminus\partial F=F$ に属するが、面は $G$ と交わらないので矛盾である。
数え上げ。面 $F$ の次数を、$\partial F$ に含まれる辺の本数（両側が $F$ に接する辺は 2 本と数える）と定める。各辺はちょうど二つの面に接するか、両側で同じ面に接するので、面の次数の総和は $2m$ である。各面の境界は閉路を含むので、面の次数はその閉路の長さ以上であり、したがって $g$ 以上である。よって $gf\le2m$ である。prop-planar-euler-components により $f=1+c-n+m\ge2-n+m$（$c\ge1$）だから
$$ g(2-n+m)\le gf\le2m, $$
すなわち $(g-2)m\le g(n-2)$ を得る。