AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_outerplanar

def

A simple graph G is outerplanar (simple_graph_is_outerplanar G) if neither the complete graph on 4 vertices K_4 nor the complete bipartite graph K_{2,3} is a minor of G.

Statement

def simple_graph_is_outerplanar {V : Type*} (G : SimpleGraph V) : Prop
Defined in
Chartrand and Harary (1967), Planar Permutation Graphs
Verified
16 Nov 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 1

Read back from the Lean

Given a type V and a simple graph G on V, simple_graph_is_outerplanar G is defined to hold if and only if both: 1. The complete graph on 4 vertices, (⊤ : SimpleGraph (Fin 4)), is not a minor of G (in the sense of simple_graph_is_minor), and 2. The complete bipartite graph completeBipartiteGraph (Fin 2) (Fin 3) is not a minor of G (in the sense of simple_graph_is_minor).

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 simple graph G is outerplanar if neither K_4 nor K_{2,3} is a minor of G. -/
def simple_graph_is_outerplanar {V : Type*} (G : SimpleGraph V) : Prop := ¬ simple_graph_is_minor (⊤ : SimpleGraph (Fin 4)) G ∧
  ¬ simple_graph_is_minor (completeBipartiteGraph (Fin 2) (Fin 3)) G
See it in the graphDiscuss this resultChallenge it