What is Kuratowski’s theorem?

Kuratowski’s theorem is a fundamental result in topological graph theory. It deals with the characterization of planar graphs, or graphs that have no edge intersections when drawn in a plane. According to this theorem, proposed by the mathematician Kazimierz Kuratowski in 1930: “A finite graph is planar if and only if it does not contain a subdivision of either K₅ or K_3,3.”

Non-planar graphs: K₅ and K_3,3

A graph that cannot be drawn without its edges intersecting is known as a non-planar graph in graph theory. Kuratowski’s theorem states that two non-planar graphs are K₅ and K_3,3.

K₅

K₅ is a complete graph of five vertices having one edge between every pair of vertices. There are ten edges, and each vertex is directly connected to the other vertex by an edge. Since the graph cannot be drawn without its edges crossing one another, in a plane, it is referred to as non-planar.

K_3,3

K_3,3 is a complete bipartite graph. It has two sets of three vertices, where each vertex in one set is connected to the vertex in the other set. Hence, the K_3,3 graph has nine edges.

Proof of Kuratowski’s theorem

We will demonstrate Kuratowski’s theorem through the following statement:

“If a graph is planar, it must not contain K₅ and K_3,3 as a subdivision.”

Let’s prove the contrapositive statement: “If a graph contains either K₅ or K_3,3 as a subdivision, then it is non-planar.” Let's see the example given in the slides below. 

For K₅: Assume we have a graph X, which has K₅ as its subdivision. This means that within X, there lie some edges that have been replaced with paths, resulting in a graph that can be transformed into K₅ without changing the vertices’ connectivity. Since it is established that K₅ is non-planar, if X contains K₅ as its subdivision, X must be non-planar.

For K_3,3: Similarly, suppose we have a graph X that contains K_3,3 as its subdivision. If X has a subdivision of K_3,3, then some edges in X have been replaced with paths to form a graph that can be transformed into K_3,3. This implies that X, containing K_3,3 as a subdivision, is non-planar.

This proves the contrapositive statement that if a graph contains a subdivision of K₅ or K_3,3, then the graph is non-planar. According to the concept of logical equivalence: “If a graph is planar, it must not contain K₅ and K_3,3 as a subdivision” is also true.

Conclusion

Kuratowski’s theorem is a very powerful tool in graph theory as it has various applications in network design, computer science, circuit theory, and others. In network design, Kuratowski’s theorem aids in ensuring if a particular network can be created without overlapping. In computer science, it can be used in graph database management and layout algorithms for software visualization.