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