Editing Planar graph (section)

=== Kuratowski's and Wagner's theorems ===
{{tesseract_graph_nonplanar_visual_proof.svg}}
The [[Poland|Polish]] mathematician [[Kazimierz Kuratowski]] provided a characterization of planar graphs in terms of [[Forbidden graph characterization|forbidden graphs]], now known as [[Kuratowski's theorem]]:

:A [[finite graph]] is planar [[if and only if]] it does not contain a [[Glossary of graph theory#subgraph|subgraph]] that is a [[subdivision (graph theory)|subdivision]] of the [[complete graph]] {{math|''K''{{sub|5}}}} or the [[complete bipartite graph]] {{math|''K''{{sub|3,3}}}} ([[utility graph]]).

A [[subdivision (graph theory)|subdivision]] of a graph results from inserting vertices  into edges (for example, changing an edge {{nowrap|• —— • to • — • — • )}} zero or more times.
[[Image:Nonplanar no subgraph K 3 3.svg|thumb|An example of a graph with no {{math|''K''{{sub|5}}}} or {{math|''K''{{sub|3,3}}}} subgraph. However, it contains a subdivision of {{math|''K''{{sub|3,3}}}} and is therefore non-planar.]]

Instead of considering subdivisions, [[Wagner's theorem]] deals with [[minor (graph theory)|minors]]:

:A finite graph is planar if and only if it does not have {{math|''K''{{sub|5}}}} or {{math|''K''{{sub|3,3}}}} as a [[minor (graph theory)|minor]].

A [[minor (graph theory)|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.

[[File:Kuratowski.gif|thumb|484px|An animation showing that the [[Petersen graph]] contains a minor isomorphic to the {{math|''K''{{sub|3,3}}}} graph, and is therefore non-planar]]

[[Klaus Wagner (mathematician)|Klaus Wagner]] asked more generally whether any minor-closed class of graphs is determined by a finite set of "[[forbidden minor]]s". This is now the [[Robertson–Seymour theorem]], proved in a long series of papers. In the language of this theorem, {{math|''K''{{sub|5}}}} and {{math|''K''{{sub|3,3}}}} are the forbidden minors for the class of finite planar graphs.