クラトフスキーの定理

$K_5$ と $K_{3,3}$（したがってそれらの細分）が非平面的であることは、オイラーの公式 $V - E + F = 2$ から従う：$V \ge 3$ 頂点の平面グラフは $E \le 3V - 6$ を満たし（$V=5, E=10$ の $K_5$ を除外）、三角形を含まなければ $E \le 2V - 4$ を満たす（二部グラフで $V=6, E=9$ の $K_{3,3}$ を除外）。逆方向については、極小な非平面反例 $G$ をとり、それが3連結であることを示し、辺 $e = \{u,v\}$ を縮約または削除して、$G - e$ の平面埋め込みの面の周りの道が $e$ を交差なく配置することをどう妨げるかを解析すると、$K_5$ または $K_{3,3}$ の細分が現れざるを得ないことが分かる。