Kuratowski's theorem

from Wikipedia, the free encyclopedia

The Kuratowski's theorem (after Kazimierz Kuratowski ) is a set of the graph theory , the important statements on planar graphs makes and the question of the planarity (planarity) of a graph answered.


Animation: the Petersen graph contains as a minor and is therefore not planar.

In general terms, a graph is planar (flattenable) if and only if it is possible to draw the graph in the plane in such a way that the edges of the graph do not intersect. The edges may only touch in the nodes of the graph.

The following two graphs are planar, the planarity of only becoming apparent when you draw differently.

Fig. 1: Example graphs G1 and G2

The graphs K 5 and K 3,3

Fig. 2:
Fig. 3:

Kuratowski's theorem uses two special graphs: and . When it is the complete graph with 5 nodes (see Fig. 2), in a completely bipartite graph , which is divided into two each three-element subsets (see Fig. 3). Both graphs are not planar. They are actually the smallest non-planar graphs around, which follows directly from Kuratowski's theorem.

Kuratowski's theorem

Kuratowski's theorem says that a graph is planar if and only if it does not have a subgraph that is a subdivision graph of the or the . A subdivision graph is obtained by repeatedly replacing an edge with an incident pair of edges. Alternatively, one can formulate that a graph is planar if and only if it contains neither the nor that as a minor .

See also