PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
Kuratowski's theorem (Theorem)

A finite graph is planar if and only if it contains no subgraph that is isomorphic to or is a subdivision of $K_5$ or $K_{3,3}$ where $K_5$ is the complete graph of order 5 and $K_{3,3}$ is the complete bipartite graph with 3 vertices in each of the halfs. Wagner's theorem is an equivalent later result.

References

1
Kazimierz Kuratowski.
Sur le problème des courbes gauches en topologie.
Fund. Math., 15:271-283, 1930.




"Kuratowski's theorem" is owned by bbukh. [ full author list (2) | owner history (1) ]
(view preamble | get metadata)

View style:

See Also: planar graph, Wagner's theorem

Keywords:  planar
Log in to rate this entry.
(view current ratings)

Cross-references: equivalent, Wagner's theorem, vertices, complete bipartite graph, order, complete graph, subdivision, isomorphic, subgraph, contains, planar, graph, finite
There are 4 references to this entry.

This is version 8 of Kuratowski's theorem, born on 2001-11-12, modified 2004-03-27.
Object id is 764, canonical name is KuratowskisTheorem.
Accessed 10155 times total.

Classification:
AMS MSC05C10 (Combinatorics :: Graph theory :: Topological graph theory, imbedding)

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)