AFTD Auto-Formalizing Theoretical Domains

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