AFTD Auto-Formalizing Theoretical Domains

ghz_even_card_of_perfect_matching

lemmaverified

For 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 V is even.

Statement

lemma ghz_even_card_of_perfect_matching {V : Type*} [Fintype V]
    (G : SimpleGraph V) (M : Finset (Sym2 V)) (hM : ghz_is_perfect_matching G M) :
    Even (Fintype.card V)
Source
arXiv:2610.22190 Section 2
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…
Used by 1

Read back from the Lean

For any finite type $V$, any simple graph $G$ on $V$, and any finite set $M$ of unordered pairs of vertices (elements of Sym2 V), if $M$ is a perfect matching of $G$ (meaning every pair in $M$ is an edge of $G$, and every vertex $v : V$ belongs to a unique pair in $M$), then the cardinality of $V$ is even.

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 finite simple graph with a perfect matching has an even number of vertices. -/
lemma ghz_even_card_of_perfect_matching {V : Type*} [Fintype V]
    (G : SimpleGraph V) (M : Finset (Sym2 V)) (hM : ghz_is_perfect_matching G M) :
    Even (Fintype.card V) := by
  classical
  rw [ghz_is_perfect_matching] at hM
  obtain ⟨hmem, hcov⟩ := hM
  -- every vertex lies in at most one matching edge (uniqueness form)
  have huniq : ∀ v (e e' : Sym2 V), e ∈ M → v ∈ e → e' ∈ M → v ∈ e' → e = e' := by
    intro v e e' he hv he' hv'
    obtain ⟨e0, _he0, hu⟩ := hcov v
    exact (hu e ⟨he, hv⟩).trans (hu e' ⟨he', hv'⟩).symm
  -- the vertices are the disjoint union of the vertex sets of the matching edges
  have hunion : Finset.univ = M.biUnion (fun e => e.toFinset) := by
    ext v
    simp only [Finset.mem_univ, Finset.mem_biUnion, Sym2.mem_toFinset]
    constructor
    · intro _
      obtain ⟨e, he, _⟩ := hcov v
      exact ⟨e, he.1, he.2⟩
    · intro _
      trivial
  have hdisj : (M : Set (Sym2 V)).PairwiseDisjoint (fun e => e.toFinset) := by
    intro e he e' he' hne
    show Disjoint e.toFinset e'.toFinset
    rw [Finset.disjoint_left]
    intro v hv hv'
    exact hne (huniq v e e' he (Sym2.mem_toFinset.mp hv) he' (Sym2.mem_toFinset.mp hv'))
  have hcard : Fintype.card V = ∑ e ∈ M, e.toFinset.card := by
    rw [← Finset.card_univ, hunion, Finset.card_biUnion hdisj]
  -- each matching edge has exactly two endpoints, since it lies in the edge set (no loops)
  have htwo : ∀ e ∈ M, e.toFinset.card = 2 := by
    intro e he
    exact Sym2.card_toFinset_of_not_isDiag e (SimpleGraph.not_isDiag_of_mem_edgeSet G (hmem e he))
  rw [hcard, Finset.sum_const_nat htwo]
  exact ⟨M.card, by ring⟩
See it in the graphDiscuss this resultChallenge it