AFTD Auto-Formalizing Theoretical Domains

is_minimal_k_factor_critical

def

A simple graph G is minimal k-factor-critical if G is k-factor-critical and for every edge e of G, the graph G - e is not k-factor-critical.

Statement

def is_minimal_k_factor_critical {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) : Prop
Defined in
arXiv:2611.09072, Section 1
Verified
09 Nov 2026
Axioms
none listed
Built on 1
  • is_k_factor_criticalA simple graph G on a finite vertex type V is k-factor-critical if for every subset S of V with cardinality k, the induced subgraph on Sᶜ…

Read back from the Lean

For a finite type V, a simple graph G on V, and a natural number k, is_minimal_k_factor_critical G k asserts that: 1. G is $k$-factor-critical: for every subset S of V with cardinality k, the induced subgraph of G on the complement of S has a perfect matching. 2. G is minimal with respect to edge deletion: for every edge e of G, deleting e from G produces a graph that is not $k$-factor-critical.

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 G is minimal k-factor-critical if G is k-factor-critical and deleting any edge yields a graph that is not k-factor-critical. -/
def is_minimal_k_factor_critical {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) : Prop := is_k_factor_critical G k ∧ ∀ e ∈ G.edgeSet, ¬ is_k_factor_critical (G.deleteEdges {e}) k
See it in the graphDiscuss this resultChallenge it