information:highlighting
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 subdivision of a graph results from inserting vertices into edges (for example, changing an edge —— to — —) zero or more times.

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

A minor of a graph results from taking a subgraph and repeatedly contracting an edge into a vertex, with each neighbor of the original end-vertices becoming a neighbor of the new vertex.

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 are the forbidden minors for the class of finite planar graphs.