AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it