平面グラフ

この一つの恒等式が、辺数の上界や $K_5$ と $K_{3,3}$ の非平面性を含め、平面グラフに関するほぼすべての他の事実の源であり、短く完全に初等的な帰納法で証明される。

基底段階。$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$ が成り立つ。

これは平面性を二つの小さな禁止パターンだけで完全かつ検証可能に特徴づけるものであり、存在に関する問い(交差のない描き方が見つかるか)を二つの具体的な障害のどちらかを探す問題に変える。

$K_5$ と $K_{3,3}$ 自体が平面的でない理由。$K_5$ は $V=5$ 個の頂点と $E=10$ 本の辺を持つが、辺の上界 $E \le 3V - 6$ は $10 \le 3(5)-6=9$ を要求し、矛盾するので $K_5$ は平面的でない。$K_{3,3}$ は $V=6$ 個の頂点と $E=9$ 本の辺を持つ2部グラフである。平面的な2部グラフはより厳しい上界 $E \le 2V - 4$ を満たさねばならず、$9 \le 2(6)-4=8$ を要求するが、これも矛盾するので $K_{3,3}$ も平面的でない。

細分は非平面性を保つ(易しい方向)。グラフ $H$ がグラフ $G$ の細分($G$ の各辺を内部互いに素な道で置き換えたもの)であり、$G$ が平面的でないなら、$H$ も平面的にはなり得ない:$H$ のどんな交差のない描画も、各道の内部にある次数2の頂点を消してそれを一本の辺へとまっすぐにし直すだけで $G$ の描画に変えられ、これは新たな交差を生まない。したがって $K_5$ または $K_{3,3}$ の細分を部分グラフとして含むどんなグラフも自動的に平面的でなく、これが定理の必要方向を証明する。

逆方向(難しい方向)の概略。任意の非平面グラフがそのような細分を含まねばならないことが本質的に深い部分であり、1930年にクラトフスキーによって、また同値なマイナーに基づく形で1937年にワグナーによって独立に証明された。議論は、$K_5$ も $K_{3,3}$ の細分も含まない仮想的な最小の非平面グラフを取り、矛盾を導くことで進む:連結性に関するメンガーの定理を用いて、まずグラフが3連結である場合に帰着し(小さい頂点カットを持つグラフはそのカットに沿ってより小さいか平面的な部分に分割し、後で組み立て直せる)、次に最小サイズの3連結な非平面グラフはすでに二つの禁止された細分のいずれかを含むことを直接示す。この連結性による構造的な帰着こそが、定理の本当の難しさが宿る場所である。

結論。両方向を組み合わせると、グラフが平面的であるのは、まさに二つの禁止された細分の両方を避けている場合であり、完全な特徴づけが得られる。