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.

© 1996-9

1999-05-26