AFTD Auto-Formalizing Theoretical Domains

ghz_is_perfect_matching

def

A 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 of G and every vertex v : V is incident to a unique edge in M (there exists a unique e in M such that v ∈ e).

Statement

def ghz_is_perfect_matching {V : Type*} [Fintype V] (G : SimpleGraph V) (M : Finset (Sym2 V)) : Prop
Defined in
scout/2610-22190-connectivity-bounds-for-ghz-graphs.md:149
Verified
21 Oct 2026
Axioms
none listed
Used by 8
  • 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_cut_parity_eq_of_perfect_matchingFor 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…
  • 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…
  • is_ghz_graphFor any type V : Type* with [Fintype V], a simple graph G on V with edge colouring c : Sym2 V → ℕ and edge weighting w : Sym2 V → ℂ…
  • ghz_matching_index_le_min_degreeFor any finite type V with decidable equality and any connected simple graph G on V with decidable adjacency, the matching index…
  • ghz_matching_cross_cut_ge_two_of_evenFor 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…
  • ghz_vertex_colouring_weightFor any type V : Type* with [Fintype V], given a simple graph G on V, edge weights w : Sym2 V → ℂ, edge colouring c : Sym2 V → ℕ, and…
  • ghz_matching_indexFor any type V : Type* with [Fintype V], the matching index ghz_matching_index G of a simple graph G on V is the supremum (sSup in ℕ) of…

Read back from the Lean

For a finite type V, a simple graph G on V, and a finite set of unordered pairs M of elements of V, ghz_is_perfect_matching G M asserts that: 1. Every element e ∈ M is an edge of G (e ∈ G.edgeSet), and 2. For every vertex v : V, there exists a unique e ∈ M such that v ∈ e (that is, v is an endpoint of e). In other words, M is a perfect matching (a 1-factor) of the graph G.

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 set of edges is a perfect matching in G if every edge in M is an edge of G and every vertex in V is incident to a unique edge in M. -/
def ghz_is_perfect_matching {V : Type*} [Fintype V] (G : SimpleGraph V) (M : Finset (Sym2 V)) : Prop := (∀ e ∈ M, e ∈ G.edgeSet) ∧ ∀ v : V, ∃! e ∈ M, v ∈ e
See it in the graphDiscuss this resultChallenge it