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

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

Copyright © 1999-2000 SciMathMN