Planar Graph - Kuratowski's and Wagner's Theorems

Kuratowski's and Wagner's Theorems

The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of forbidden graphs, now known as Kuratowski's theorem:

A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K₅ (the complete graph on five vertices) or K_3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).

A subdivision of a graph results from inserting vertices into edges (for example, changing an edge •——• to •—•—•) zero or more times. Equivalent formulations of this theorem, also known as "Theorem P" include

A finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to K₅ or K_3,3.

In the Soviet Union, Kuratowski's theorem was known as the Pontryagin–Kuratowski theorem, as its proof was allegedly first given in Pontryagin's unpublished notes. By a long-standing academic tradition, such references are not taken into account in determining priority, so the Russian name of the theorem is not acknowledged internationally.

Instead of considering subdivisions, Wagner's theorem deals with minors:

A finite graph is planar if and only if it does not have K₅ or K_3,3 as a minor.

Klaus Wagner asked more generally whether any minor-closed class of graphs is determined by a finite set of "forbidden minors". This is now the Robertson–Seymour theorem, proved in a long series of papers. In the language of this theorem, K₅ and K_3,3 are the forbidden minors for the class of finite planar graphs.