Wagner's Theorem

Wagner's theorem states that a graph is planar iff it does not contain K_5 or K_(3,3) as a graph minor.

See also

Kuratowski's Theorem, Robertson-Seymour Theorem

Explore with Wolfram|Alpha


Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin: Springer-Verlag, p. 269, 2008.Kuratowski, C. "Sur le problème des courbes gauches en topologie." Fund. Math. 15, 217-283, 1930.Wagner, K. "Über eine Eigenschaft der ebenen Komplexe." Math. Ann. 114, 570-590, 1937.

Cite this as:

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