AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_planar

def

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

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
See it in the graphDiscuss this resultChallenge it