AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_induced_matching

def

A set E of edges of a simple graph G is an induced matching if no two edges of E conflict in G.

Statement

def simple_graph_is_induced_matching {V : Type*} (G : SimpleGraph V) (E : Set G.edgeSet) : Prop
Defined in
arXiv:2611.10883, Section 2
Verified
10 Nov 2026
Axioms
none listed
Built on 1
  • simple_graph_edge_conflictTwo distinct edges e₁, e₂ ∈ G.edgeSet of a simple graph G conflict if they share an endpoint or are joined by an edge of G.

Read back from the Lean

Given a simple graph G on vertex type V and a set of edges E : Set G.edgeSet, simple_graph_is_induced_matching G E asserts that for all edges e₁, e₂ : G.edgeSet, if e₁ ∈ E and e₂ ∈ E, then e₁ and e₂ do not conflict in G (that is, ¬ simple_graph_edge_conflict G e₁ e₂).

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 set of edges is an induced matching if no two of its edges conflict. -/
def simple_graph_is_induced_matching {V : Type*} (G : SimpleGraph V) (E : Set G.edgeSet) : Prop := ∀ ⦃e₁ e₂⦄, e₁ ∈ E → e₂ ∈ E → ¬ simple_graph_edge_conflict G e₁ e₂
See it in the graphDiscuss this resultChallenge it