simple_graph_is_planar
A simple graph G is planar by Wagner's criterion if neither the complete graph on 5 vertices nor the complete bipartite graph K_{3,3} is a minor of G.
Statement
def simple_graph_is_planar {V : Type*} (G : SimpleGraph V) : Prop
- Defined in
- Wagner 1937; Diestel, Graph Theory (5th ed.), Theorem 4.4.2
- Verified
- 26 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_is_minorA graph H is a minor of a graph G if there exists a family of pairwise disjoint, non-empty, connected subsets B_u of V(G) indexed by u in…
- Used by 3
- exists_planar_all_powers_well_covered_diam_eq_threeThere exists a finite connected simple planar graph G with at least two vertices whose diameter is exactly 3 and such that every positive…
- not_planar_all_powers_well_covered_characterizationIt is not the case that every finite connected simple planar graph G with at least two vertices whose powers G^d are all well-covered is…
- cycle_seven_is_planarThe 7-cycle graph C_7 is planar.
Read back from the Lean
For a simple graph G on vertex type V, simple_graph_is_planar G is defined to hold if and only if both of the following conditions are satisfied:
1. G does not have the complete graph on 5 vertices (⊤ : SimpleGraph (Fin 5)) as a minor.
2. G does not have the complete bipartite graph $K_{3,3}$ (completeBipartiteGraph (Fin 3) (Fin 3)) as a minor.
Here, a graph H on vertex type U is a minor of G (simple_graph_is_minor H G) if there exists a family of branch sets B : U → Set V such that:
- for every vertex u : U, the induced subgraph G.induce (B u) is connected (which in particular implies B u is nonempty),
- for all vertices u, v : U, if u ≠ v, then B u and B v are disjoint, and
- for all vertices u, v : U, if H.Adj u v, then there exist x ∈ B u and y ∈ B v such that G.Adj x y.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A graph is planar in the sense of Wagner if it contains neither K_5 nor K_{3,3} as a minor. -/ def simple_graph_is_planar {V : Type*} (G : SimpleGraph V) : Prop := ¬ simple_graph_is_minor (⊤ : SimpleGraph (Fin 5)) G ∧ ¬ simple_graph_is_minor (completeBipartiteGraph (Fin 3) (Fin 3)) G