PlanetMath: Kuratowski's theorem

(more info)

Math for the people, by the people.

Main Menu

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 or $K_{3,3}$ , where 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)

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 8655 times total.

Classification:

05C10 (Combinatorics :: Graph theory :: Topological graph theory, imbedding)

Pending Errata and Addenda

None.[ View all 3 ]

Discussion

forum policy

No messages.

Interact