Kuratowski's theorem

In

of ${\displaystyle K_{5}}$ (the complete graph on five vertices) or of ${\displaystyle K_{3,3}}$ (a ).

Statement

A

this makes no difference to their graph-theoretic characterization.

A

of one or more edges. Kuratowski's theorem states that a finite graph ${\displaystyle G}$ is planar if it is not possible to subdivide the edges of ${\displaystyle K_{5}}$ or ${\displaystyle K_{3,3}}$, and then possibly add additional edges and vertices, to form a graph isomorphic to ${\displaystyle G}$. Equivalently, a finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to ${\displaystyle K_{5}}$ or ${\displaystyle K_{3,3}}$.

Kuratowski subgraphs

If ${\displaystyle G}$ is a graph that contains a subgraph ${\displaystyle H}$ that is a subdivision of ${\displaystyle K_{5}}$ or ${\displaystyle K_{3,3}}$, then ${\displaystyle H}$ is known as a Kuratowski subgraph of ${\displaystyle G}$.^[1] With this notation, Kuratowski's theorem can be expressed succinctly: a graph is planar if and only if it does not have a Kuratowski subgraph.

The two graphs ${\displaystyle K_{5}}$ and ${\displaystyle K_{3,3}}$ are nonplanar, as may be shown either by a

. Additionally, subdividing a graph cannot turn a nonplanar graph into a planar graph: if a subdivision of a graph ${\displaystyle G}$ has a planar drawing, the paths of the subdivision form curves that may be used to represent the edges of ${\displaystyle G}$ itself. Therefore, a graph that contains a Kuratowski subgraph cannot be planar. The more difficult direction in proving Kuratowski's theorem is to show that, if a graph is nonplanar, it must contain a Kuratowski subgraph.

Algorithmic implications

A Kuratowski subgraph of a nonplanar graph can be found in

Usually, non-planar graphs contain a large number of Kuratowski-subgraphs. The extraction of these subgraphs is needed, e.g., in branch and cut algorithms for crossing minimization. It is possible to extract a large number of Kuratowski subgraphs in time dependent on their total size.^[4]

History

Kazimierz Kuratowski published his theorem in 1930.^[5] The theorem was independently proved by Orrin Frink and Paul Smith, also in 1930,^[6] but their proof was never published. The special case of cubic planar graphs (for which the only minimal forbidden subgraph is ${\displaystyle K_{3,3}}$) was also independently proved by Karl Menger in 1930.^[7] Since then, several new proofs of the theorem have been discovered.^[8]

In the Soviet Union, Kuratowski's theorem was known as either the Pontryagin–Kuratowski theorem or the Kuratowski–Pontryagin theorem,^[9] as the theorem was reportedly proved independently by Lev Pontryagin around 1927.^[10] However, as Pontryagin never published his proof, this usage has not spread to other places.^[11]

Related results

A closely related result, Wagner's theorem, characterizes the planar graphs by their minors in terms of the same two forbidden graphs ${\displaystyle K_{5}}$ and ${\displaystyle K_{3,3}}$. Every Kuratowski subgraph is a special case of a minor of the same type, and while the reverse is not true, it is not difficult to find a Kuratowski subgraph (of one type or the other) from one of these two forbidden minors; therefore, these two theorems are equivalent.^[12]

An extension is the Robertson–Seymour theorem.

See also

• Kelmans–Seymour conjecture, that 5-connected nonplanar graphs contain a subdivision of ${\displaystyle K_{5}}$

References