Kuratowski's theorem

Kuratowski's theorem is the statement that a graph is planar if and only if it has no subgraph that can be "collapsed" to the complete graph K(5) or the bipartite graph K(3, 3).

A graph is "collapsed" in two ways:

• by removing each vertex of degree one and the edge to that vertex
• by replacing with a single edge each vertex of degree 2 and its two incident edges.
For example, in the graph pictured to the left below, vertex H has degree 1, so it and edge GH are removed. Vertices C and D have degree 2; each of them, along with their incident edges, is replaced by a single edge. The resulting collapsed graph appears to the right below.

Because the graph on the right is complete graph K(5), we conclude from Kuratowski's theorem that the graph to the left above is not planar.

A more formal way of saying that one graph can be collapsed to another is to say that the graphs are homeomorphic. Then Kuratowski's Theorem is the claim that a graph is planar if and only if it has no subgraph homeomorphic to K(5) or K(3, 3).