AFTD Auto-Formalizing Theoretical Domains

simple_graph_link_matching_cover_certificate

def

The graph has a matching M and a vertex set Q of size at most |M| such that all edges avoiding Q belong to M.

Statement

def simple_graph_link_matching_cover_certificate {V : Type*} [DecidableEq V] (G : SimpleGraph V) : Prop
Source
arXiv:2610.15269, Section 2, the matching-cover condition for a reducible link.
Verified
02 Nov 2026
Axioms
none listed

Lean source view module on GitHub

def simple_graph_link_matching_cover_certificate {V : Type*} [DecidableEq V] (G : SimpleGraph V) : Prop := ∃ (M : Finset (Sym2 V)) (Q : Finset V), (∀ e ∈ M, e ∈ G.edgeSet) ∧ (∀ e ∈ M, ∀ f ∈ M, e ≠ f → ∀ v ∈ e, v ∉ f) ∧ Q.card ≤ M.card ∧ (∀ e ∈ G.edgeSet, (∀ v ∈ Q, v ∉ e) → e ∈ M)
See it in the graphDiscuss this resultChallenge it