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.
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.