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
- odd_cycle_is_minimal_factor_criticalFor every integer n ≥ 1, the odd cycle graph C_{2n+1} is minimal factor-critical.
- IsMinimalFactorCriticalA 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…
- odd_cycle_is_factor_criticalFor every integer n ≥ 1, the odd cycle graph C_{2n+1} is factor-critical.
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