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