graph_is_forcing_matching
def
A 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.
Statement
def graph_is_forcing_matching {V : Type*} (G : SimpleGraph V) (S : G.Subgraph) : Prop
- Defined in
- arXiv:2611.11813 Section 1
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Used by 3
- graph_min_forcing_numThe minimum forcing number graph_min_forcing_num G of a simple graph G is the infimum in ℕ∞ of the extended cardinalities S.edgeSet.encard…
- 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_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 type V, a simple graph G on V, and a subgraph S of G, graph_is_forcing_matching G S asserts that:
1. S is a matching in G (S.IsMatching), and
2. There exists a unique subgraph M of G such that M is a perfect matching in G (M.IsPerfectMatching) and S is a subgraph of M (S ≤ M).
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 subgraph S of G is a forcing matching if S is a matching contained in a unique perfect matching of G. -/ def graph_is_forcing_matching {V : Type*} (G : SimpleGraph V) (S : G.Subgraph) : Prop := S.IsMatching ∧ ∃! M : G.Subgraph, M.IsPerfectMatching ∧ S ≤ M