Wagner's theorem

Wagner's theorem characterizes planar graphs: a graph is planar if and only if it has no minor isomorphic to K₅ or K₃,₃.

Planar graph: A graph that can be drawn in the plane with edges meeting only at shared endpoints. Wagner’s theorem identifies exactly which finite graphs belong to this class.
K₅: The complete graph on five vertices, with an edge joining every pair. It is one of the two forbidden minors that certify nonplanarity.
Klaus Wagner: A German mathematician known for foundational work in graph theory, including the theorem bearing his name. His 1937 result established the forbidden-minor characterization of planar graphs.
Robertson–Seymour theorem: The theorem that every minor-closed graph property can be characterized by finitely many excluded minors. It generalizes the finite-obstruction pattern exemplified by Wagner’s theorem.
Graph contraction: An operation that merges the endpoints of an edge into one vertex, removing loops and merging parallel edges when working with simple graphs. Repeated contractions help produce K₅ or K₃,₃ as a minor.
K₃,₃: The complete bipartite graph with two parts of three vertices each. It is the second forbidden minor in Wagner’s characterization.
1937: A year in the twentieth century, Gregorian calendar. Wagner published his characterization of planar graphs in this year.
Treewidth: A graph parameter measuring how closely a graph resembles a tree. Planar graphs have structural constraints on treewidth that support algorithms and decomposition results.
Graph embedding: A drawing of a graph on a surface in which vertices are distinct points and edges intersect only at shared endpoints. Planarity means an embedding exists on the plane, the property the theorem characterizes.
Kuratowski's theorem: A graph is planar if and only if it contains no subdivision of K₅ or K₃,₃. It gives an equivalent obstruction test using subdivisions rather than minors.

Linked from 4 pages

Graph structure theoremCompared with: It is a concrete excluded-minor characterization, unlike the general structural description.