Kuratowski’s graphs refer to two specific graphs, K₅ and K_3,3. This theorem states that a graph is planar (it can be drawn on a plane without any edges crossing) if and only if it does not contain a subgraph that is a subdivision of K₅​ (the complete graph on five vertices) or K_3,3.​ (the complete bipartite graph on two sets of three vertices). In this article, we will learn about Kuratowski’s theorem which states that a graph is planar if and only if it contains no subdivision of K₅ or K_3,3.

What is Kuratowski’s Theorem?

In graph theory, Kuratowski’s theorem is a mathematical restriction on the characteristics of a planar graph, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph subdivision of K₅ (the complete graph on five vertices) or of K_3,3 (a complete bipartite graph on six vertices).

Kuratowski’s first graph is the non-planar graph with the smallest number of vertices, and Kuratowski’s second graph is the non-planar graph with the smallest number of edges.

What is Planarity?

A graph is planar if and only if it does not contain a subgraph that is a subdivision of K₅ or K_3,3. Kuratowski’s theorem states that a graph is planar if and only if it doesn’t contain a subgraph isomorphic to a subdivision of K₅ or K_3,3. Both K₅ and K_3,3 are non-planar. Also, all the graphs that contain a subgraph that is a subdivision of either K3,3 or K5 are non-planar.

Kuratowski’s 1st Graph with Diagram

A complete graph with 5 vertices is called Kuratowski’s first graph. The graph is generally denoted by K5.

Kuratowski’s first non-planar graph (K5)

Kuratowski’s 2nd Graph with Diagram

A regular connected graph with 6 vertices and 9 edges is called Kuratowski’s second graph. The graph is generally denoted by K3,3.

Kuratowski’s second non-planar graph (K3,3)

Chromatic Number of Kuratowski’s Graphs

The chromatic number of a graph is the minimum number of colors needed to color the vertices of the graph such that no two adjacent vertices have the same color. In other words, it is the smallest number of colors needed to color the vertices of the graph so that no adjacent vertices have the same color.

• Chromatic number of Kuratowski’s first non-plannar graphs (K₅) is 5.
• Chromatic number of Kuratowski’s second non-plannar graphs (K_3,3) is 2.

Conclusion

A Kuratowski graph is a subdivision of K5 or K3,3. It follows from Euler’s Formula that neither K5 nor K3,3 is planar. The planarity of a graph, whether a graph can be drawn on a plane in a way that no edges intersect. It can be seen that K5 and K3,3 are non-planar. So, a graph that contain subgraph of that is a subdivision of either K3,3 or K5 is also non-planar.

Frequently Asked Questions on Kuratowski’s Graphs – FAQs

What is coplanarity?

Two lines in three-dimensional space are said to be coplanar if there is a plane that includes them both.

What is complete graph?

A complete graph is a graph in which each vertex is connected to every other vertex. A complete graph is an undirected graph where every pair of distinct vertices is connected by a unique edge.

What is a bipartite graph?

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets X and Y such that every edge connects a vertex in X to one in Y.