Kuratowski's Theorem

# 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.