クラトフスキーの定理

$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連結な非平面グラフはすでに二つの禁止された細分のいずれかを含むことを直接示す。この連結性による構造的な帰着こそが、定理の本当の難しさが宿る場所である。

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