graph_min_forcing_num
def
The minimum forcing number graph_min_forcing_num G of a simple graph G is the infimum in ℕ∞ of the extended cardinalities S.edgeSet.encard over all subgraphs S of G that are forcing matchings of G.
Statement
noncomputable def graph_min_forcing_num {V : Type*} (G : SimpleGraph V) : ℕ∞
- Defined in
- arXiv:2611.11813 Section 1
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 1
- graph_is_forcing_matchingA subgraph S of a simple graph G is a forcing matching if S is a matching and there is a unique perfect matching M of G with S ≤ M.
- Used by 3
- op_1371_min_forcing_num_upper_bound_achievableThere exists a natural number n, a bipartite simple graph G on Fin n, a field F with ringChar F ≠ 2, such that G admits an involutory…
- op_1371_odd_improved_upper_bound_achievableThere exists a natural number n, a bipartite simple graph G on Fin n, a field F with ringChar F ≠ 2, and a natural number k such that G…
- op_1371_even_upper_bound_achievableThere exists a natural number n, a bipartite simple graph G on Fin n, a field F with ringChar F ≠ 2, and a natural number k such that G…
Read back from the Lean
Given a simple graph G on a type V, graph_min_forcing_num G is defined as the infimum in ℕ∞ (the extended natural numbers WithTop ℕ) of the extended cardinality of the edge set of S (S.edgeSet.encard), over all subgraphs S of G such that graph_is_forcing_matching G S holds.
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
/-- The minimum forcing number f(G) of a simple graph G is the infimum in ℕ∞ of the sizes of forcing matchings. -/ noncomputable def graph_min_forcing_num {V : Type*} (G : SimpleGraph V) : ℕ∞ := ⨅ (S : G.Subgraph) (_ : graph_is_forcing_matching G S), S.edgeSet.encard