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
- op_1764_outerplanar_underlying_color_graph_of_injectiveFor every finite outerplanar simple graph G on type V in the sense of simple_graph_is_outerplanar G and every injective vertex coloring c…
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