Kuratowski's theorem gives a structural test for planarity: a finite graph is planar exactly when it contains neither a subdivision of K5 nor a subdivision of K3,3. section 15.1.1
Use the theorem to reason about non-planarity:
- K5 is the complete graph on five vertices, while K3,3 is the complete bipartite graph with two parts of three vertices. section 15.1.1
- A graph containing either forbidden structure, possibly with edges subdivided into paths, cannot have a planar embedding. section 15.1.1
- Every smaller subgraph of K5 or K3,3 is planar, making these two graphs the minimal non-planar cases in this characterization. section 15.2.1
Distinguishing a tempting candidate
K4 may appear non-planar when drawn naively, but moving one vertex produces a crossing-free embedding. Removing any edge from K5 likewise removes its unavoidable obstruction. section 15.2.1
The theorem proves whether a graph is planar, but it does not directly compute the minimum number of crossings for a non-planar graph. Finding that crossing number for generic graphs is NP-complete. section 15.3.1
