MATtours of discrete mathematics

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.

collapsing a graph

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