AFTD Auto-Formalizing Theoretical Domains

ghz_matching_index_le_min_degree

theoremverifiedformalization

For any finite type V with decidable equality and any connected simple graph G on V with decidable adjacency, the matching index ghz_matching_index G is at most the minimum degree G.minDegree.

Statement

theorem ghz_matching_index_le_min_degree {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (h_conn : G.Connected) :
    ghz_matching_index G ≤ G.minDegree
Formalizes
arXiv:2610.22190 Observation 7
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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_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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. If $G$ is connected, then the GHZ matching index of $G$ (ghz_matching_index G) is less than or equal to the minimum degree of $G$ (G.minDegree).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is proved by showing that the matching index of G is bounded above by the degree of every vertex v, from which the bound by the minimum degree follows because G is connected and hence has a nonempty vertex set. For any vertex v and edge colouring c, every monochromatic vertex colouring induced by a perfect matching is constant and therefore uniquely determined by its value at v. Since v is covered by an edge e = {v, u} of the matching, this value must be c({v, u}) for some neighbor u of v, which bounds the number of such monochromatic colourings by deg(v). Taking the supremum over all valid GHZ colourings yields the vertex degree bound, and taking the minimum over all vertices completes the proof.

  1. The evaluation map vc ↦ vc(v) is injective on the set S of monochromatic vertex colourings compatible with c, so |S| equals the cardinality of its image under evaluation at v.

    We define S as the set of vertex colourings that are both compatible with the edge colouring c on some perfect matching of G and monochromatic (constant across all vertices). Given any two colourings vc₁ and vc₂ in S that agree at v, the monochromaticity condition means each takes a constant value on all vertices, so vc₁(u) = vc₁(v) = vc₂(v) = vc₂(u) for all u ∈ V, whence vc₁ = vc₂. Since evaluation at v is injective on S, the cardinality of S equals the cardinality of its image.

    lines 8–20

      let S := { vc : V → ℕ |
        (∃ M : Finset (Sym2 V), ghz_is_perfect_matching G M ∧ ∀ e ∈ M, ∀ u : V, u ∈ e → vc u = c e) ∧
        (∃ k : ℕ, ∀ u : V, vc u = k) }
      have hinj : Set.InjOn (fun vc => vc v) S := by
        intro vc1 h1 vc2 h2 heq
        change vc1 v = vc2 v at heq
        rcases h1.2 with ⟨k1, hk1⟩
        rcases h2.2 with ⟨k2, hk2⟩
        ext u
        have hu1 : vc1 u = vc1 v := by rw [hk1 u, hk1 v]
        have hu2 : vc2 u = vc2 v := by rw [hk2 u, hk2 v]
        rw [hu1, heq, ← hu2]
      have hcard : S.ncard = ((fun vc => vc v) '' S).ncard := (hinj.ncard_image).symm
  2. The image of S under evaluation at v is contained in the set of colours {c(s(v, u)) : u ∈ N(v)} of edges incident to v.

    Let x be in the image of S under evaluation at v, so x = vc(v) for some vc ∈ S. By definition of S, vc agrees with c on the edges of some perfect matching M of G. Since M is a perfect matching, there is a unique edge e ∈ M containing v, and e is an edge of G. Writing e = s(x₀, y₀) via Sym2.inductionOn, the incidence condition v ∈ e means v = x₀ or v = y₀ by Sym2.mem_iff. In either case, the other endpoint is a neighbor u of v in G by SimpleGraph.mem_edgeSet (using Sym2.eq_swap if v = y₀). Since vc(v) = c(e) = c(s(v, u)), the value vc(v) belongs to {c(s(v, u)) : u ∈ N(v)}.

    lines 21–36

    uses Sym2.inductionOn, Sym2.mem_iff, SimpleGraph.mem_edgeSet, Sym2.eq_swap

      have hsub : (fun vc => vc v) '' S ⊆ (fun u : V => c s(v, u)) '' (G.neighborSet v) := by
        rintro x ⟨vc, hvc, rfl⟩
        dsimp
        rcases hvc.1 with ⟨M, hM, hc⟩
        rcases hM.2 v with ⟨e, ⟨heM, hve⟩, -⟩
        have he_edge : e ∈ G.edgeSet := hM.1 e heM
        have hvc_v : vc v = c e := hc e heM v hve
        induction' e using Sym2.inductionOn with x y
        rw [Sym2.mem_iff] at hve
        rcases hve with rfl | rfl
        · rw [SimpleGraph.mem_edgeSet] at he_edge
          rw [hvc_v]
          exact ⟨y, he_edge, rfl⟩
        · rw [SimpleGraph.mem_edgeSet] at he_edge
          rw [hvc_v]
          refine ⟨x, he_edge.symm, by rw [Sym2.eq_swap]⟩
  3. The cardinality of S is at most the degree of v.

    By subset inclusion, the cardinality of the image (vc ↦ vc(v)) '' S is at most that of {c(s(v, u)) : u ∈ N(v)} via Set.ncard_le_ncard (with finiteness from Set.toFinite). The cardinality of this image is at most the cardinality of the neighborhood N(v) by Set.ncard_image_le. Converting the neighborhood to a finset gives |N(v)| = G.degree v using Set.ncard_coe_finset. Linear arithmetic (linarith) chains these inequalities with |S| = |(vc ↦ vc(v)) '' S| to conclude |S| ≤ G.degree v.

    lines 37–47

    uses Set.ncard_le_ncard, Set.toFinite, Set.ncard_image_le, Set.ncard_coe_finset

      have hle1 : ((fun vc => vc v) '' S).ncard ≤ ((fun u : V => c s(v, u)) '' (G.neighborSet v)).ncard :=
        Set.ncard_le_ncard hsub (Set.toFinite _)
      have hle2 : ((fun u : V => c s(v, u)) '' (G.neighborSet v)).ncard ≤ (G.neighborSet v).ncard :=
        Set.ncard_image_le (Set.toFinite _)
      have hdeg : (G.neighborSet v).ncard = G.degree v := by
        have h : (G.neighborSet v).ncard = (G.neighborFinset v : Set V).ncard := by
          congr 1
          exact (G.coe_neighborFinset v).symm
        rw [h, Set.ncard_coe_finset, G.card_neighborFinset_eq_degree]
      show S.ncard ≤ G.degree v
      linarith
  4. For every vertex v, the matching index ghz_matching_index G is at most the degree of v.

    By definition, the matching index is the supremum sSup setD, where setD is the set of cardinalities |S| arising from valid GHZ graph colourings. If setD is nonempty, every d ∈ setD is bounded by G.degree v by ghz_matching_index_le_min_degree_ncard_le, so sSup setD ≤ G.degree v by csSup_le. If setD is empty (Set.not_nonempty_iff_eq_empty), the supremum is ⊥ = 0 by csSup_empty, which is at most G.degree v by Nat.zero_le.

    lines 51–62

    uses csSup_le, ghz_matching_index_le_min_degree_ncard_le, Set.not_nonempty_iff_eq_empty, csSup_empty, Nat.zero_le

      let setD := { d : ℕ | ∃ (c : Sym2 V → ℕ) (w : Sym2 V → ℂ), is_ghz_graph G c w ∧
        d = Set.ncard { vc : V → ℕ |
          (∃ M : Finset (Sym2 V), ghz_is_perfect_matching G M ∧ ∀ e ∈ M, ∀ u : V, u ∈ e → vc u = c e) ∧
          (∃ k : ℕ, ∀ u : V, vc u = k) } }
      change sSup setD ≤ G.degree v
      by_cases hne : setD.Nonempty
      · apply csSup_le hne
        rintro d ⟨c, w, hw, rfl⟩
        exact ghz_matching_index_le_min_degree_ncard_le G v c
      · rw [Set.not_nonempty_iff_eq_empty] at hne
        rw [hne, csSup_empty]
        exact Nat.zero_le _
  5. Bounding the matching index at every vertex implies that it is at most the minimum degree of G.

    Because G is connected, its vertex set V is nonempty. For any nonempty finite graph, an upper bound that holds for the degree of every vertex also holds for the minimum degree by SimpleGraph.le_minDegree_of_forall_le_degree. Applying the vertex-degree bound ghz_matching_index_le_min_degree_degree_le to all v ∈ V completes the proof.

    lines 68–71

    uses SimpleGraph.le_minDegree_of_forall_le_degree, ghz_matching_index_le_min_degree_degree_le

      have : Nonempty V := h_conn.nonempty
      apply SimpleGraph.le_minDegree_of_forall_le_degree
      intro v
      exact ghz_matching_index_le_min_degree_degree_le G v
Sym2.inductionOn
Every unordered pair in Sym²(V) is of the form s(x, y) for some x, y ∈ V.
Sym2.mem_iff
An element a belongs to the unordered pair s(b, c) if and only if a = b or a = c.
SimpleGraph.mem_edgeSet
The unordered pair s(v, w) belongs to the edge set of G if and only if v and w are adjacent in G.
Sym2.eq_swap
The unordered pair s(a, b) equals s(b, a).
Set.ncard_le_ncard
If a set s is a subset of a finite set t, then |s| ≤ |t|.
Set.toFinite
A set whose subtype is finite is a finite set.
Set.ncard_image_le
The image of a finite set under any function has cardinality at most that of the domain set.
Set.ncard_coe_finset
The cardinality of a finset coerced to a set equals its finset cardinality.
csSup_le
In a conditionally complete lattice, if a nonempty set is bounded above by a, then its supremum is at most a.
ghz_matching_index_le_min_degree_ncard_le
For any vertex v and edge colouring c, the number of monochromatic vertex colourings compatible with c on some perfect matching is at most the degree of v.
Set.not_nonempty_iff_eq_empty
A set is not nonempty if and only if it is empty.
csSup_empty
The supremum of the empty set in a conditionally complete linear order with bottom is ⊥.
Nat.zero_le
Zero is less than or equal to any natural number.
SimpleGraph.le_minDegree_of_forall_le_degree
In a nonempty finite graph, if a number k is at most the degree of every vertex, then k is at most the minimum degree of the graph.
ghz_matching_index_le_min_degree_degree_le
For any vertex v, the matching index of G is at most the degree of v.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open scoped Classicallemma ghz_matching_index_le_min_degree_ncard_le {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V)    (c : Sym2 V → ℕ) :    Set.ncard { vc : V → ℕ |      (∃ M : Finset (Sym2 V), ghz_is_perfect_matching G M ∧ ∀ e ∈ M, ∀ u : V, u ∈ e → vc u = c e) ∧      (∃ k : ℕ, ∀ u : V, vc u = k) } ≤ G.degree v := by  let S := { vc : V → ℕ |    (∃ M : Finset (Sym2 V), ghz_is_perfect_matching G M ∧ ∀ e ∈ M, ∀ u : V, u ∈ e → vc u = c e) ∧    (∃ k : ℕ, ∀ u : V, vc u = k) }  have hinj : Set.InjOn (fun vc => vc v) S := by    intro vc1 h1 vc2 h2 heq    change vc1 v = vc2 v at heq    rcases h1.2 with ⟨k1, hk1⟩    rcases h2.2 with ⟨k2, hk2⟩    ext u    have hu1 : vc1 u = vc1 v := by rw [hk1 u, hk1 v]    have hu2 : vc2 u = vc2 v := by rw [hk2 u, hk2 v]    rw [hu1, heq, ← hu2]  have hcard : S.ncard = ((fun vc => vc v) '' S).ncard := (hinj.ncard_image).symm  have hsub : (fun vc => vc v) '' S ⊆ (fun u : V => c s(v, u)) '' (G.neighborSet v) := by    rintro x ⟨vc, hvc, rfl⟩    dsimp    rcases hvc.1 with ⟨M, hM, hc⟩    rcases hM.2 v with ⟨e, ⟨heM, hve⟩, -⟩    have he_edge : e ∈ G.edgeSet := hM.1 e heM    have hvc_v : vc v = c e := hc e heM v hve    induction' e using Sym2.inductionOn with x y    rw [Sym2.mem_iff] at hve    rcases hve with rfl | rfl    · rw [SimpleGraph.mem_edgeSet] at he_edge      rw [hvc_v]      exact ⟨y, he_edge, rfl⟩    · rw [SimpleGraph.mem_edgeSet] at he_edge      rw [hvc_v]      refine ⟨x, he_edge.symm, by rw [Sym2.eq_swap]⟩  have hle1 : ((fun vc => vc v) '' S).ncard ≤ ((fun u : V => c s(v, u)) '' (G.neighborSet v)).ncard :=    Set.ncard_le_ncard hsub (Set.toFinite _)  have hle2 : ((fun u : V => c s(v, u)) '' (G.neighborSet v)).ncard ≤ (G.neighborSet v).ncard :=    Set.ncard_image_le (Set.toFinite _)  have hdeg : (G.neighborSet v).ncard = G.degree v := by    have h : (G.neighborSet v).ncard = (G.neighborFinset v : Set V).ncard := by      congr 1      exact (G.coe_neighborFinset v).symm    rw [h, Set.ncard_coe_finset, G.card_neighborFinset_eq_degree]  show S.ncard ≤ G.degree v  linarithlemma ghz_matching_index_le_min_degree_degree_le {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) :    ghz_matching_index G ≤ G.degree v := by  let setD := { d : ℕ | ∃ (c : Sym2 V → ℕ) (w : Sym2 V → ℂ), is_ghz_graph G c w ∧    d = Set.ncard { vc : V → ℕ |      (∃ M : Finset (Sym2 V), ghz_is_perfect_matching G M ∧ ∀ e ∈ M, ∀ u : V, u ∈ e → vc u = c e) ∧      (∃ k : ℕ, ∀ u : V, vc u = k) } }  change sSup setD ≤ G.degree v  by_cases hne : setD.Nonempty  · apply csSup_le hne    rintro d ⟨c, w, hw, rfl⟩    exact ghz_matching_index_le_min_degree_ncard_le G v c  · rw [Set.not_nonempty_iff_eq_empty] at hne    rw [hne, csSup_empty]    exact Nat.zero_le _/-- The matching index of a connected simple graph is bounded above by its minimum degree. -/theorem ghz_matching_index_le_min_degree {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (h_conn : G.Connected) :    ghz_matching_index G ≤ G.minDegree := by  have : Nonempty V := h_conn.nonempty  apply SimpleGraph.le_minDegree_of_forall_le_degree  intro v  exact ghz_matching_index_le_min_degree_degree_le G v
See it in the graphDiscuss this resultChallenge it