Kuratowski's Theorem

Kuratowski's Theorem is critically important in determining if a graph is planar or not and we state it below.

Theorem 1 (Kuratowski's Theorem): A graph is planar if and only if it does not contain any subdivisions of the graphs $K_5$ or $K_{3,3}$.

We will not provide a formula proof, however, we will apply this theorem extensively. It turns out that this theorem is true since every non-planar graph is obtained by adding vertices and/or edges to a subdivision of either $K_5$ or $K_{3,3}$. Hence if we can identify that a subdivision of either of these graphs exists within our graph, then we can easily determine if the graph is planar or not.

For example, the following graph:

Notice that this graph is simply a subdivision of $K_{3,3}$ as shown:

Hence the graph is NOT planar.

It turns out that if a graph $G$ contains no subgraph that is itself a contraction of $K_5$ or $K_{3,3}$ then the graph itself is also planar. We will omit the proof.