is_k_factor_critical
def
A 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ᶜ has a perfect matching.
Statement
def is_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
- Used by 1
- is_minimal_k_factor_criticalA 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.
Read back from the Lean
Given a finite type V, a simple graph G on V, and a natural number k, is_k_factor_critical G k asserts that for every finset S of vertices of V such that the cardinality of S is k, there exists a subgraph M of the induced subgraph G[V \ S] (the induced subgraph on the complement of S) 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 G on a finite vertex type V is k-factor-critical if for every subset S ⊆ V of size k, the induced subgraph on Sᶜ has a perfect matching. -/ def is_k_factor_critical {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) : Prop := ∀ S : Finset V, S.card = k → ∃ M : (G.induce (S : Set V)ᶜ).Subgraph, M.IsPerfectMatching