AFTD Auto-Formalizing Theoretical Domains

IsFactorCritical

def

A simple graph G on a vertex type V is factor-critical if for every vertex v : V, the induced subgraph of G on {v}ᶜ has a perfect matching, that is, there exists a subgraph M of G.induce ({v}ᶜ : Set V) such that M.IsPerfectMatching.

Statement

def IsFactorCritical {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2611.09072 Section 1
Verified
09 Nov 2026
Axioms
none listed
Used by 3

Read back from the Lean

For a simple graph G on a vertex type V, IsFactorCritical G asserts that for every vertex v : V, there exists a subgraph M of the induced subgraph of G on the complement of {v} (i.e., on V \ {v}) such that M is a perfect matching.

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 is factor-critical if deleting any single vertex leaves a graph with a perfect matching. -/
def IsFactorCritical {V : Type*} (G : SimpleGraph V) : Prop := ∀ v : V, ∃ M : (G.induce ({v}ᶜ : Set V)).Subgraph, M.IsPerfectMatching
See it in the graphDiscuss this resultChallenge it