ghz_matching_index_le_min_degree
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
LinearOrderis aTotalPreorder. - 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 thanLinearOrder— 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.
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.
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
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)}.
uses
Sym2.inductionOn,Sym2.mem_iff,SimpleGraph.mem_edgeSet,Sym2.eq_swaphave 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]⟩
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.
uses
Set.ncard_le_ncard,Set.toFinite,Set.ncard_image_le,Set.ncard_coe_finsethave 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
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.
uses
csSup_le,ghz_matching_index_le_min_degree_ncard_le,Set.not_nonempty_iff_eq_empty,csSup_empty,Nat.zero_lelet 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 _
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.
uses
SimpleGraph.le_minDegree_of_forall_le_degree,ghz_matching_index_le_min_degree_degree_lehave : 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.
- The proof establishes the upper bound for the degree of an arbitrary vertex v, and uses the connectivity hypothesis only at the very end to ensure that V is nonempty, allowing the bound to transfer to the minimum degree.
- In the case where no valid GHZ colouring exists, the set of cardinalities is empty and its supremum evaluates to ⊥ = 0 under Mathlib's conventions for conditionally complete lattices on ℕ, which is trivially at most the vertex degree.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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