Kuratowski Reduction Theorem

Every nonplanar graph is a Supergraph of an expansion of the Utility Graph ${\it UG}=K_{3,3}$ or the Complete Graph $K_5$. This theorem was also proven earlier by Pontryagin (1927-1928), and later by Frink and Smith (1930). Kennedy et al. (1985) give a detailed history of the theorem, and there exists a generalization known as the Robertson-Seymour Theorem.

See also Complete Graph, Planar Graph, Robertson-Seymour Theorem, Utility Graph

References

Kennedy, J. W.; Quintas, L. V.; and Syslo, M. M. ``The Theorem on Planar Graphs.'' Historia Math. 12, 356-368, 1985.

Kuratowski, C. ``Sur l'operation A de l'analysis situs.'' Fund. Math. 3, 182-199, 1922.

Thomassen, C. ``Kuratowski's Theorem.'' J. Graph Th. 5, 225-241, 1981.

Thomassen, C. ``A Link Between the Jordan Curve Theorem and the Kuratowski Planarity Criterion.'' Amer. Math. Monthly 97, 216-218, 1990.