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:
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