The Kuratowski graph refers to a particular graph that is used to characterize planar graphs. In graph theory, a planar graph is a graph that can be drawn on a 2D plane without any of its edges crossing each other. In 1930, Kazimierz Kuratowski, a Polish mathematician, proved a fundamental theorem that establishes a criterion for determining whether a graph is planar or not.
Kuratowski's theorem states that a graph is non-planar if and only if it contains a subgraph that is a homeomorphic to either the complete graph on five vertices (denoted as K₅) or the complete bipartite graph on three vertices each (denoted as K₃,₃). Homeomorphic means that the subgraph can be obtained from K₅ or K₃,₃ by a series of edge contractions and edge deletions.
The Kuratowski graph itself is a simple graph with 11 vertices and 20 edges that serves as an example of a non-planar graph. It is formed by two copies of K₅ connected at a single vertex.
To summarize, the Kuratowski graph is an important concept in graph theory, used to demonstrate the non-planarity of graphs, and it plays a significant role in understanding the properties of planar graphs.
