Wagner's Theorem characterizes planar graphs, those that can be drawn in the plane with no crossing edges, as exactly the graphs that contain neither the complete graph on five vertices nor the complete bipartite graph on three plus three vertices as a minor. Named for Klaus Wagner, it restates Kuratowski's earlier subdivision-based characterization of planarity in terms of graph minors instead, a formulation later generalized by the Robertson-Seymour Theorem.
Facts
StatementA finite graph is planar if and only if it does not have the complete graph K5 or the complete bipartite graph K3,3 as a minor. 2 Classification
Statement FormCharacterization Theorem 1 Wagner's Theorem
Filter Results1 entry
Connections
Has Statement Form
In Branch
Source Wagner's theorem - Wikipedia
Principal Result Of
Source Klaus Wagner (Wikipedia)
Proved By
Source Wagner's theorem - Wikipedia
Sources
1. Wikipedia: Wagner's theorem
WikipediaLead section, statement-form referenceQuote, Lead section, statement-form reference
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices).
2. Wagner's theorem - Wikipedia
Lead section
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices).
History and relation to Kuratowski's theorem section
Wagner published both theorems in 1937
In Branch: Graph Theory, Lead sentence
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, s
Proved By: Klaus Wagner, Lead paragraph
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a
View the SourceKlaus Wagner (Wikipedia)
Principal Result Of: Klaus Wagner, Article textQuote, Principal Result Of: Klaus Wagner, Article text
Another result of his, also known as Wagner's theorem, is that a four-connected graph is planar if and only if it has no K5 minor.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.