Kuratowski’s Theorem

A finite graph $G$ is planar $⟺$ it has no subdivision of a Complete Graph $K_5$ or complete bipartite graph $K_{3,3}$ as a subgraph.

Proof:

The reverse direction is trivial. We apply

1. [[Planar Graph#theorem-k_5-is-non-planar|Theorem ($K_5$ is Non-Planar)]]
2. [[Planar Graph#theorem-k_33-is-non-planar|Theorem ($K_{3,3}$ is Non-Planar)]] For the forward direction, we know $G$ is planar iff every connected component is planar, and that $G$ has $K_5$ or $K_{3,3}$ iff some component does. Then for each connected component, then $G$ is planar iff each block is planar. Then $G$ contains $K_5$ or $K_{3,3}$ iff some block does.

$G$ has an ear decomposition. We can now perform induction on ears. If the graph is just a cycle $C$, then the theorem holds. Assume that Kuratowski’s Theorem holds for $G^{\prime }$, built from $k$ ears.

So, WTS if $G=G^{\prime }+P$ where $P$ is the $k$th ear is non-planar, then it must contain a $K_5$ or $K_{3,3}$ subdivision. So, we have two cases.

1. If $G^{\prime }$ is already non-planar, then we already have either subgraph as a subdivision in $G$.
2. Let $G^{\prime }$ be planar, but $G$ is not. Let $u,v$ be $P$‘s endpoints in cycle $C\subset G^{\prime }$. Then as $G$ is non-planar, we cannot draw $P$ inside cycle $C$, nor can we draw it outside. This forms $K_{3,3}$.

The last part of this proof is not fleshed out.