Kuratowski's Theorem

Every nonplanar graph contains either the utility graph K_(3,3) (i.e., the complete bipartite graph on two sets of three vertices) or the pentatope graph K_5 as a homeomorphic subgraph. These graphs are sometimes known as Kuratowski graphs.

The theorem was also proven earlier (but not published) by Pontryagin in 1927-1928, and six months later than Kuratowski by Frink and Smith (Kullman 1979; Harary 1981; Harris et al. 2000, p. 43). Kennedy et al. (1985) give a detailed history of the theorem.

See also

Complete Bipartite Graph, Complete Graph, Forbidden Minor, Kuratowski Graph, Planar Graph, Robertson-Seymour Theorem, Utility Graph, Wagner's Theorem

Explore with Wolfram|Alpha


Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin: Springer-Verlag, p. 269, 2008.Harary, F. "Kuratowski's Theorem." In Graph Theory. Reading, MA: Addison-Wesley, pp. 108-113, 1994.Harary, F. "Homage to the Memory of Kazimierz Kuratowski." J. Graph Th. 5, 217-219, 1981.Harris, J. M.; Hirst, J. L.; Mossinghoff, M. J. Combinatorics and Graph Theory. New York: Springer, 2000.Kennedy, J. W.; Quintas, L. V.; and Syslo, M. M. "The Theorem on Planar Graphs." Historia Math. 12, 356-368, 1985.Kullman, D. E. "The Utilities Problem." Math. Mag. 52, 299-302, 1979.Kuratowski, C. "Sur l'operation A de l'analysis situs." Fund. Math. 3, 182-199, 1922.Kuratowski, C. "Sur le problème des courbes gauches en topologie." Fund. Math. 15, 217-283, 1930.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 247, 1990.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.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 246-251, 2000.

Cite this as:

Weisstein, Eric W. "Kuratowski's Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications