AFTD Auto-Formalizing Theoretical Domains

ghz_matching_cross_cut_ge_two_of_even

lemmaverified

For any finite type V with decidable equality, simple graph G on V, perfect matching M of G, and subset S ⊆ V of even cardinality, if M contains at least one edge crossing the cut between S and Sᶜ, then M contains at least 2 edges crossing the cut.

Statement

lemma ghz_matching_cross_cut_ge_two_of_even {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (M : Finset (Sym2 V)) (hM : ghz_is_perfect_matching G M)
    (S : Finset V) (heven : S.card % 2 = 0)
    (hcross : (M.filter (fun e => ∃ u ∈ S, ∃ v ∈ (Sᶜ : Finset V), e = s(u, v))).card ≠ 0) :
    2 ≤ (M.filter (fun e => ∃ u ∈ S, ∃ v ∈ (Sᶜ : Finset V), e = s(u, v))).card
Source
arXiv:2610.22190 Section 4
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • ghz_matching_cross_cut_card_parityFor any finite type V with decidable equality, simple graph G on V, perfect matching M of G, and subset S ⊆ V, the number of edges in M…
  • ghz_is_perfect_matchingA set of edges M : Finset (Sym2 V) is a perfect matching in a simple graph G on a finite type V if every edge in M belongs to the edge set…

Read back from the Lean

For any finite type $V$ with decidable equality, simple graph $G$ on $V$, finite set of edges $M \subseteq \mathrm{Sym}^2(V)$, and finite subset of vertices $S \subseteq V$: If: 1. $M$ is a perfect matching of $G$ (meaning every element of $M$ is an edge of $G$, and every vertex $v \in V$ belongs to a unique edge in $M$); 2. The cardinality of $S$ is even ($|S| \equiv 0 \pmod 2$); and 3. The number of edges in $M$ that cross between $S$ and $S^c$ (i.e., edges in $M$ of the form $s(u, v)$ with $u \in S$ and $v \in S^c$) is non-zero; Then the number of edges in $M$ crossing between $S$ and $S^c$ is at least $2$.

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 perfect matching crossing an even cut must contain at least two crossing edges. -/
lemma ghz_matching_cross_cut_ge_two_of_even {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (M : Finset (Sym2 V)) (hM : ghz_is_perfect_matching G M)
    (S : Finset V) (heven : S.card % 2 = 0)
    (hcross : (M.filter (fun e => ∃ u ∈ S, ∃ v ∈ (Sᶜ : Finset V), e = s(u, v))).card ≠ 0) :
    2 ≤ (M.filter (fun e => ∃ u ∈ S, ∃ v ∈ (Sᶜ : Finset V), e = s(u, v))).card := by
  have hparity := ghz_matching_cross_cut_card_parity G M hM S
  omega
See it in the graphDiscuss this resultChallenge it