Kuratowski's Theorem

Kuratowski's Theorem tells us exactly when a graph can be drawn on a plane without any edges crossing. It says that a graph is planar if and only if it does not contain a subdivision of $K_5$ (the complete graph on 5 vertices) or $K_{3,3}$ (the complete bipartite graph with two sets of 3 vertices). A subdivision means you can replace edges with paths (by adding vertices of degree 2), but the essential structure remains the same.

Important properties

• A graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3}$.

• Subdividing edges (replacing an edge by a path) does not affect planarity.

• To prove a graph is nonplanar, it is enough to find a subdivision of $K_5$ or $K_{3,3}$ inside it.

• If you cannot find such a subdivision, you can use Euler's formula to check planarity.