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₂