Kuratowski's theorem

The set of Kuratowski ( Kazimierz Kuratowski ) is a set of graph theory, which makes important statements about planar graphs and the question of the planarity ( planarity ) of a graph answered.

Planarity

Generally speaking is a graph if and only planar ( planar ) if it is possible to plot the graph in the plane that do not intersect the edges of the graph. The edges are allowed to touch only at the nodes of the graph.

The following two graphs are planar, the planarity of only becomes apparent when one distinguishes different.

The graphs and

The set of Kuratowski uses two special graph: and. When it is the complete graph with 5 nodes ( see Figure 2), with a fully bipartite graph, which is divided into two three-element subsets ( see Figure 3). Both graphs are not planar. They are even the smallest non- planar graphs at all, which follows directly from the set of Kuratowski.

The set of Kuratowski

The set of Kuratowski states that a graph is planar if it has no subgraph that is a subdivision of the graph or the. A subdivision graph obtained by adding an edge is replaced by a repeated inzidentes edge pair. Alternatively, one can formulate that a graph is planar if it contains neither the nor the as a topological minor.