Kuratowskitétel

Kuratowskitétel, known in English as Kuratowski's theorem, is a central result in graph theory that characterizes planar graphs. It states that a finite graph is planar if and only if it contains no subgraph that is a subdivision of K5 or of K3,3.

K5 denotes the complete graph on five vertices, in which every pair of vertices is connected by an edge. K3,3 denotes the complete bipartite graph with two sets of three vertices, where every vertex in one set connects to all vertices in the other set. A subdivision of a graph is obtained by replacing edges with internally vertex‑disjoint paths, effectively inserting degree-two vertices along edges. Equivalently, a graph contains a subdivision of another graph if it has a subgraph that is homeomorphic to that graph.

Thus, Kuratowskitétel provides a topological obstruction set for planarity: a graph is non-planar exactly when it contains a subgraph that can be transformed into K5 or K3,3 by smoothing or suppressing degree-two vertices. This formalizes the intuition that K5 and K3,3 are the smallest “forbidden configurations” for planar drawings.

History and relation to other results: the theorem was proved by Kazimierz Kuratowski in 1930 and has since become a foundational tool in planarity testing. A related result is Wagner’s theorem, which characterizes planarity via minors instead of subdivisions: a graph is planar if and only if it has no K5 or K3,3 as a minor.

Applications of Kuratowskitétel include algorithmic planarity testing, graph drawing, and the study of graph embeddings, providing a concrete criterion to certify non‑planarity.