maxcut_strong_equilibrium_extend_low_degree_vertex
If a vertex has degree strictly smaller than the number k of available colors, a strong equilibrium of the induced graph obtained by deleting it extends to a strong equilibrium of the original finite graph.
Statement
theorem maxcut_strong_equilibrium_extend_low_degree_vertex {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (k : ℕ) (hd : G.degree v < k) (hsub : ∃ s : (↑(Finset.univ.erase v) : Set V) → Fin k, is_maxcut_strong_equilibrium (G.induce (↑(Finset.univ.erase v) : Set V)) s) : ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ
- Source
- Structural reduction for OP-85, the unweighted Max-k-Cut strong-equilibrium existence problem in arXiv:2610.04948, Section 4.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- maxcut_strong_equilibrium_of_saturated_vertexA coloring of a finite graph is a strong equilibrium if its restriction after deleting a vertex is a strong equilibrium and every edge…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- Used by 1
- maxcut_strong_equilibrium_reduce_connected_coreFix k. If every finite graph of minimum degree at least k whose every vertex deletion is preconnected has a strong k-color equilibrium,…
The proof, explained
The proof extends a strong equilibrium s on G - v to the entire graph G by choosing an unused color for v. Since the degree of v is strictly less than the number k of available colors, its neighbors use strictly fewer than k distinct colors, leaving at least one color c unused. Assigning color c to v ensures that all incident edges to v are cut, so v achieves its maximum possible cut utility and can never participate in any improving coalition deviation; the theorem then follows from the key lemma maxcut_strong_equilibrium_of_saturated_vertex.
Fix a strong equilibrium s on G - v, note k > 0, extend s to all vertices as s0, and collect the colors used by the neighbors of v.
Using classical logic, let A = V \ {v} be the remaining vertices and unpack the assumed strong equilibrium s on the induced subgraph G[A]. Since the degree of v is strictly less than k and degrees are non-negative, linear arithmetic (via omega) yields 0 < k. We extend s to a total coloring s0 on V by assigning an arbitrary default color 0 to v, and define used as the image under s0 of the neighbor finset of v.
classical let A : Finset V := Finset.univ.erase v obtain ⟨s, hs⟩ := hsub have hk : 0 < k := by omega let s0 : V → Fin k := fun w => if hw : w ∈ A then s ⟨w, hw⟩ else ⟨0, hk⟩ let used := (G.neighborFinset v).image s0
The number of distinct colors used by the neighbors of v is strictly less than k.
The size of used cannot exceed the number of neighbors of v (by Finset.card_image_le). In turn, the number of neighbors equals the degree of v (by G.card_neighborFinset_eq_degree), which is strictly less than k = |Fin k| by the hypothesis hd.
uses
Finset.card_image_le,G.card_neighborFinset_eq_degreehave hcard : used.card < Fintype.card (Fin k) := by calc used.card ≤ (G.neighborFinset v).card := Finset.card_image_le _ = G.degree v := G.card_neighborFinset_eq_degree v _ < Fintype.card (Fin k) := by simpa using hd
There exists an available color c not used by any neighbor of v.
By contradiction, suppose no such unused color exists. Then every color in Fin k is in used, making used equal to the universal set Finset.univ (by Finset.eq_univ_iff_forall.mpr). Its cardinality would then be k, contradicting |used| < k via Nat.lt_irrefl. Thus there is an unused color c.
uses
Finset.eq_univ_iff_forall.mpr,Nat.lt_irreflhave hc : ∃ c : Fin k, c ∉ used := by by_contra h push Not at h have heq : used = Finset.univ := Finset.eq_univ_iff_forall.mpr h rw [heq] at hcard exact (Nat.lt_irrefl _ hcard) obtain ⟨c, hc⟩ := hc
Assigning color c to v and keeping the colors of all other vertices yields a coloring σ where every neighbor of v has a color different from v.
Define σ by assigning c to v and s0(w) to every other vertex w. For any neighbor w of v, G.ne_of_adj ensures w ≠ v. Then s0(w) is in used (by Finset.mem_image.mpr and G.mem_neighborFinset), which means s0(w) ≠ c since c ∉ used. Therefore σ(w) ≠ σ(v), meaning all edges incident to v are cut.
uses
G.ne_of_adj,Finset.mem_image.mpr,G.mem_neighborFinsetlet σ : V → Fin k := fun w => if w = v then c else s0 w have hproper : ∀ w, G.Adj v w → σ w ≠ σ v := by intro w hw have hwne : w ≠ v := (G.ne_of_adj hw).symm have hwused : s0 w ∈ used := by exact Finset.mem_image.mpr ⟨w, (G.mem_neighborFinset v w).mpr hw, rfl⟩ have hne : s0 w ≠ c := by intro heq apply hc simpa [heq] using hwused simpa [σ, hwne] using hne
The restriction of σ to V \ {v} coincides with the original equilibrium s.
For any element x in V \ {v}, x ≠ v by Finset.mem_erase.mp. Evaluating σ at x gives s0(x) = s(x), so the restriction is definitionally equal to s.
uses
Finset.mem_erase.mphave hs_eq : (fun x : (↑A : Set V) => σ x.1) = s := by funext x have hxne : x.1 ≠ v := (Finset.mem_erase.mp x.2).1 simp [σ, s0, hxne, x.2]
The extended coloring σ is a max-cut strong equilibrium of G.
We provide σ as the existential witness using Exists.intro. Because σ cuts every edge incident to v, vertex v already attains its maximum possible utility (its degree), so it cannot strictly improve in any coalition deviation. By maxcut_strong_equilibrium_of_saturated_vertex, any such saturated extension of a strong equilibrium on G - v is a strong equilibrium of G.
uses
Exists.intro,maxcut_strong_equilibrium_of_saturated_vertexapply Exists.intro σ apply maxcut_strong_equilibrium_of_saturated_vertex G v σ hproper exact hs_eq ▸ hs
Finset.card_image_le- The size of the image of a finite set under a function is at most the size of the domain set.
G.card_neighborFinset_eq_degree- In a simple graph, the number of neighbors of a vertex equals its degree.
Finset.eq_univ_iff_forall.mpr- A finset in a finite type equals the universal finset if and only if it contains every element of the type.
Nat.lt_irrefl- Strict inequality on natural numbers is irreflexive: n < n is false for every n.
G.ne_of_adj- Adjacent vertices in a simple graph are distinct (no self-loops).
Finset.mem_image.mpr- An element b is in the image of s under f if there exists some a in s with f a = b.
G.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
Finset.mem_erase.mp- If an element belongs to s with v erased, it is distinct from v and belongs to s.
Exists.intro- Proves an existential proposition ∃ x, P x by providing an explicit witness w and a proof of P w.
maxcut_strong_equilibrium_of_saturated_vertex- If a coloring cuts every edge incident to a vertex v (so v achieves maximal cut utility) and restricts to a strong equilibrium on G - v, then it is a strong equilibrium of G.
- To define the set of colors used by the neighbors before choosing a color for v, the formal proof first extends s to a function s0 on all of V by assigning an arbitrary default color to v (which is valid because k > 0). This placeholder color is immediately overridden by the chosen color c in the final coloring σ.
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 Finsettheorem maxcut_strong_equilibrium_extend_low_degree_vertex {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (k : ℕ) (hd : G.degree v < k) (hsub : ∃ s : (↑(Finset.univ.erase v) : Set V) → Fin k, is_maxcut_strong_equilibrium (G.induce (↑(Finset.univ.erase v) : Set V)) s) : ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by classical let A : Finset V := Finset.univ.erase v obtain ⟨s, hs⟩ := hsub have hk : 0 < k := by omega let s0 : V → Fin k := fun w => if hw : w ∈ A then s ⟨w, hw⟩ else ⟨0, hk⟩ let used := (G.neighborFinset v).image s0 have hcard : used.card < Fintype.card (Fin k) := by calc used.card ≤ (G.neighborFinset v).card := Finset.card_image_le _ = G.degree v := G.card_neighborFinset_eq_degree v _ < Fintype.card (Fin k) := by simpa using hd have hc : ∃ c : Fin k, c ∉ used := by by_contra h push Not at h have heq : used = Finset.univ := Finset.eq_univ_iff_forall.mpr h rw [heq] at hcard exact (Nat.lt_irrefl _ hcard) obtain ⟨c, hc⟩ := hc let σ : V → Fin k := fun w => if w = v then c else s0 w have hproper : ∀ w, G.Adj v w → σ w ≠ σ v := by intro w hw have hwne : w ≠ v := (G.ne_of_adj hw).symm have hwused : s0 w ∈ used := by exact Finset.mem_image.mpr ⟨w, (G.mem_neighborFinset v w).mpr hw, rfl⟩ have hne : s0 w ≠ c := by intro heq apply hc simpa [heq] using hwused simpa [σ, hwne] using hne have hs_eq : (fun x : (↑A : Set V) => σ x.1) = s := by funext x have hxne : x.1 ≠ v := (Finset.mem_erase.mp x.2).1 simp [σ, s0, hxne, x.2] apply Exists.intro σ apply maxcut_strong_equilibrium_of_saturated_vertex G v σ hproper exact hs_eq ▸ hs