## Kuratowski Reduction Theorem

Every nonplanar graph is a Supergraph of an expansion of the Utility Graph or the Complete Graph . 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.

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.