AFTD Auto-Formalizing Theoretical Domains

IsMinimalFactorCritical

def

A simple graph G on a vertex type V is minimal factor-critical if G is factor-critical and for every edge e ∈ G.edgeSet, the graph G.deleteEdges {e} obtained by deleting e is not factor-critical.

Statement

def IsMinimalFactorCritical {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2611.09072 Section 1
Verified
09 Nov 2026
Axioms
none listed
Built on 1
  • IsFactorCriticalA 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…
Used by 1

Read back from the Lean

For a type V and a simple graph G on V, IsMinimalFactorCritical G asserts that: 1. G is factor-critical: for every vertex v : V, the induced subgraph of G on V \ {v} (the complement of {v}) contains a subgraph M that is a perfect matching; and 2. For every edge e in G.edgeSet, the graph G.deleteEdges {e} (obtained by removing e from G) is not factor-critical (i.e., there exists some vertex v : V for which the induced subgraph of G \ {e} on V \ {v} has no 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 minimal factor-critical if it is factor-critical and deleting any edge destroys factor-criticality. -/
def IsMinimalFactorCritical {V : Type*} (G : SimpleGraph V) : Prop := IsFactorCritical G ∧ ∀ e ∈ G.edgeSet, ¬ IsFactorCritical (G.deleteEdges {e})
See it in the graphDiscuss this resultChallenge it