Graph Theory Questions Long
Kuratowski's theorem, also known as Kuratowski's planarity criterion, is a fundamental result in graph theory that provides a necessary and sufficient condition for a graph to be planar. It was first formulated by the Polish mathematician Kazimierz Kuratowski in 1930.
The theorem states that a graph is non-planar if and only if it contains a subgraph that is homeomorphic to either the complete graph K₅ (the complete graph on five vertices) or the complete bipartite graph K₃,₃ (the complete bipartite graph with three vertices in each part).
To understand the theorem, we need to define the concept of homeomorphism. Two graphs are said to be homeomorphic if one can be obtained from the other by a sequence of edge contractions, edge deletions, and vertex deletions. In simpler terms, a graph is homeomorphic to another if they have the same "shape" or structure.
Kuratowski's theorem essentially states that if a graph contains a subgraph that can be transformed into either K₅ or K₃,₃ by contracting edges, deleting edges, or deleting vertices, then the original graph is non-planar. In other words, if we can find a subgraph that looks like K₅ or K₃,₃ within the given graph, then the graph cannot be drawn on a plane without any edge crossings.
Conversely, if a graph does not contain a subgraph homeomorphic to K₅ or K₃,₃, then it is planar. This means that it is possible to draw the graph on a plane without any edges crossing over each other.
Kuratowski's theorem is a powerful tool in graph theory as it provides a simple and effective way to determine whether a graph is planar or not. It has numerous applications in various fields, including computer science, network design, and circuit layout.