AFTD Auto-Formalizing Theoretical Domains

ghz_cut_parity_eq_of_perfect_matching

lemmaverified

For any finite type V with decidable equality and any simple graph G on V with a perfect matching M (ghz_is_perfect_matching G M), the cardinality of any subset S : Finset V and the cardinality of its complement Sᶜ have the same parity modulo 2.

Statement

lemma ghz_cut_parity_eq_of_perfect_matching {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (M : Finset (Sym2 V)) (hM : ghz_is_perfect_matching G M)
    (S : Finset V) :
    S.card % 2 = (Sᶜ : Finset V).card % 2
Source
arXiv:2610.22190 Section 4
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • ghz_even_card_of_perfect_matchingFor any finite type V and any simple graph G on V, if M is a perfect matching of G (ghz_is_perfect_matching G M), then the cardinality of…
  • 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

Let V be a finite type with decidable equality. Let G be a simple graph on V, and let M be a finite set of 2-element subsets (unordered pairs) of V. Assume hM: M is a perfect matching of G (every edge in M is an edge of G, and every vertex v ∈ V belongs to a unique edge in M). For any subset S of V, the cardinality of S modulo 2 is equal to the cardinality of its complement Sᶜ modulo 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

/-- In a finite graph with a perfect matching, both sides of any vertex cut have the same parity. -/
lemma ghz_cut_parity_eq_of_perfect_matching {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (M : Finset (Sym2 V)) (hM : ghz_is_perfect_matching G M)
    (S : Finset V) :
    S.card % 2 = (Sᶜ : Finset V).card % 2 := by
  have h := ghz_even_card_of_perfect_matching G M hM
  rw [Nat.even_iff] at h
  have hsum : S.card + (Sᶜ : Finset V).card = Fintype.card V := Finset.card_add_card_compl S
  omega
See it in the graphDiscuss this resultChallenge it