maxcut_optimal_strong_of_degree_le
For every k ≥ 1: on every finite simple graph whose maximum degree is at most 2k − 1, every optimal coloring of the unweighted Max-k-Cut game is a strong equilibrium. In terms of the open problem, Δ*(k) ≥ 2k − 1.
Statement
theorem maxcut_optimal_strong_of_degree_le (k : ℕ) (hk : 1 ≤ k) :
maxcut_optimal_strong_up_to_degree k (2 * k - 1)- Formalizes
- arXiv:2610.04948, Corollary 9 (originally arXiv:1810.09278, Proposition 9), stated there for k ≥ 2; the Lean version allows k ≥ 1 (k = 1 is trivial). Proof follows the paper's internal-conflict counting: optimal colorings are Nash, so each vertex has at most one same-colored neighbour, and the deviation identity (Lemma 7) then rules out every strong deviation
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- maxcut_optimal_strong_up_to_degreeFor k and D: on every finite simple graph of maximum degree at most D, every optimal coloring of the Max-k-Cut game with k colors is a…
- maxcut_optimal_same_color_leAt an optimal coloring σ of the Max-k-Cut game, for every vertex v and every color c, the number of neighbours of v with color σ(v) is at…
- maxcut_welfare_splitFor any set S of players, the welfare of a coloring is A + 2B + C, where A counts bichromatic adjacent ordered pairs inside S, B those…
- maxcut_utility_sum_splitFor any set S, the total utility of the members of S is A + B, with A the bichromatic adjacent ordered pairs inside S and B those from S…
- maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
- Used by 2
- maxcut_op89_exists_of_max_degree_leFor every integer k ≥ 3 and every finite simple graph G whose maximum degree is at most 2k - 1, the unweighted Max-k-Cut game admits an…
- maxcut_strong_equilibrium_exists_of_card_leFor every k ≥ 1 and every finite simple graph on at most 2k vertices, the Max-k-Cut game has an optimal coloring that is a strong…
The proof, explained
The proof proceeds by contradiction: suppose an optimal coloring σ admits a strong deviation (S, τ) by a nonempty coalition S, where every vertex in S strictly increases its utility. First, the degree bound ≤ 2k - 1 combined with optimality implies that each vertex shares its color with at most one neighbor, which bounds the increase in internal cut edges within S by at most |S|. Expressing total welfare and utility sums in terms of the cut decomposition across S and Sᶜ, the deviation must increase total welfare by at least 2|S| - |S| = |S| ≥ 1. This contradicts the optimality of σ, which requires W(τ) ≤ W(σ).
Suppose for contradiction that there exists a strong deviation from the optimal coloring.
Assume classical logic and consider a graph G with maximum degree at most 2k - 1, an optimal coloring σ, and a candidate strong deviation (S, τ). Unpacking the definition of strong deviation gives that S is nonempty (hne), τ agrees with σ outside S (hagree), and every vertex v ∈ S achieves strictly greater utility under τ than under σ (hgain). The goal is to reach False.
classical intro V _ G _ hdeg σ hopt S τ hdev obtain ⟨hne, hagree, hgain⟩ := hdev
Under the optimal coloring σ, every vertex shares its color with at most one neighbor.
Fix a vertex v. Partitioning its neighbors by their assigned color classes using `Finset.card_eq_sum_card_fiberwise`, `Finset.mem_coe.2`, `Finset.mem_univ`, and `Finset.filter_filter`, the degree of v is the sum of the sizes of these color classes. By the maximum degree assumption, this degree is at most 2k - 1 (`SimpleGraph.card_neighborFinset_eq_degree`, `SimpleGraph.neighborFinset_eq_filter`). Because σ is optimal, v has at least as many neighbors in every color class c as in its own color class σ(v) (`maxcut_optimal_same_color_le`). Summing this lower bound over all k colors gives k * |{w ∈ N(v) : σ(w) = σ(v)}| ≤ deg(v) ≤ 2k - 1 (`Finset.sum_le_sum`, `Finset.sum_const`, `Finset.card_univ`, `Fintype.card_fin`, `smul_eq_mul`). If v shared its color with 2 or more neighbors, this product would be at least 2k (`Nat.mul_le_mul_left`), contradicting 2k ≤ 2k - 1.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_coe.2,Finset.mem_univ,Finset.filter_filter,SimpleGraph.card_neighborFinset_eq_degree,SimpleGraph.neighborFinset_eq_filter,Finset.sum_le_sum,maxcut_optimal_same_color_le,Finset.sum_const,Finset.card_univ,Fintype.card_fin,smul_eq_mul,Nat.mul_le_mul_left-- at most one neighbour shares each vertex's color have hmono : ∀ v, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1 := by intro v have hsum : (Finset.univ.filter fun w => G.Adj v w).card = ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := by rw [Finset.card_eq_sum_card_fiberwise (f := σ) (t := Finset.univ) (fun _ _ => Finset.mem_coe.2 (Finset.mem_univ _))] simp only [Finset.filter_filter] have hdv : (Finset.univ.filter fun w => G.Adj v w).card ≤ 2 * k - 1 := by have := hdeg v rwa [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter] at this have hlow : ∑ _c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := Finset.sum_le_sum fun c _ => maxcut_optimal_same_color_le G σ hopt v c simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hlow by_contra hc have : k * 2 ≤ k * (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := Nat.mul_le_mul_left k (by omega) omega
Total welfare and the sum of utilities on S decompose across S and Sᶜ, with cut edges inside Sᶜ remaining unchanged.
By `maxcut_welfare_split`, total welfare decomposes for both σ and τ into cut edges within S, twice the cut edges between S and Sᶜ, and cut edges within Sᶜ. By `maxcut_utility_sum_split`, the sum of utilities on S decomposes into cut edges within S plus cut edges between S and Sᶜ. Because τ agrees with σ on Sᶜ (`hagree`, `Finset.mem_compl.1`), the cut edges entirely within Sᶜ are identical under both colorings (`Finset.sum_congr`).
uses
maxcut_welfare_split,Finset.sum_congr,Finset.mem_compl.1,maxcut_utility_sum_splithave hS := maxcut_welfare_split G σ S have hT := maxcut_welfare_split G τ S have hC : ∑ x ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj x w ∧ τ w ≠ τ x then 1 else 0 : ℕ) = ∑ x ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj x w ∧ σ w ≠ σ x then 1 else 0 : ℕ) := by refine Finset.sum_congr rfl fun x hx => Finset.sum_congr rfl fun w hw => ?_ rw [hagree x (Finset.mem_compl.1 hx), hagree w (Finset.mem_compl.1 hw)] have hUS := maxcut_utility_sum_split G σ S have hUT := maxcut_utility_sum_split G τ S
The sum of utilities on S increases by at least |S| under τ.
Each vertex v ∈ S strictly increases its utility under τ, so utility(τ, v) ≥ utility(σ, v) + 1 (`Nat.succ_le_of_lt`). Summing over all vertices in S yields ∑_{v ∈ S} utility(σ, v) + |S| ≤ ∑_{v ∈ S} utility(τ, v) (`Finset.sum_le_sum`, `Finset.sum_add_distrib`).
uses
Finset.sum_le_sum,Nat.succ_le_of_lt,Finset.sum_add_distribhave hgains : ∑ v ∈ S, maxcut_utility G σ v + S.card ≤ ∑ v ∈ S, maxcut_utility G τ v := by have := Finset.sum_le_sum fun v hv => Nat.succ_le_of_lt (hgain v hv) simpa [Finset.sum_add_distrib] using this
Pointwise, whether an edge is cut by τ is bounded by its cut status under σ plus its monochromatic status under σ.
For any pair of vertices v, w, we split on whether {v, w} is an edge cut by τ (`em`). If it is, then under σ either σ(w) ≠ σ(v) or σ(w) = σ(v) (`if_pos`), so at least one term on the right-hand side is 1. If {v, w} is not cut by τ, the indicator on the left-hand side is 0, which is trivially at most the right-hand side (`if_neg`).
uses
em,if_pos,if_neghave hpt : ∀ v w, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤ (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := by intro v w rcases em (G.Adj v w ∧ τ w ≠ τ v) with h1 | h1 · rw [if_pos h1] rcases em (σ w = σ v) with h2 | h2 · rw [if_pos (⟨h1.1, h2⟩ : G.Adj v w ∧ σ w = σ v)]; omega · rw [if_pos (⟨h1.1, h2⟩ : G.Adj v w ∧ σ w ≠ σ v)]; omega · rw [if_neg h1]; omega
The internal cut edges within S under τ exceed those under σ by at most |S|.
Summing the pointwise edge bound over all pairs v, w ∈ S (`Finset.sum_le_sum`, `Finset.sum_add_distrib`), the internal cut edges under τ are bounded by those under σ plus the sum over v ∈ S of neighbors in S sharing the color σ(v). For each v ∈ S, its monochromatic neighbors in S are a subset of its monochromatic neighbors in the entire graph (`Finset.sum_le_sum_of_subset`, `Finset.subset_univ`, `Finset.card_filter`), which is at most 1 by the earlier step `hmono`. Summing 1 over all vertices in S adds at most |S| (`Finset.sum_add_distrib`).
uses
Finset.sum_le_sum,Finset.sum_add_distrib,Finset.sum_le_sum_of_subset,Finset.subset_univ,Finset.card_filterhave hA : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤ ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + S.card := by calc ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤ ∑ v ∈ S, (∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + 1) := by refine Finset.sum_le_sum fun v _ => ?_ calc ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤ ∑ w ∈ S, ((if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) := Finset.sum_le_sum fun w _ => hpt v w _ = ∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := Finset.sum_add_distrib _ ≤ _ := by have : ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) ≤ 1 := by calc ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) ≤ ∑ w, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := Finset.sum_le_sum_of_subset (Finset.subset_univ S) _ = (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := (Finset.card_filter _ _).symm _ ≤ 1 := hmono v omega _ = _ := by simp [Finset.sum_add_distrib]
The deviation strictly increases total welfare, contradicting the optimality of σ.
Because S is nonempty, |S| ≥ 1 (`Finset.card_pos.2`). By optimality of σ, total welfare cannot strictly increase: W(τ) ≤ W(σ). However, from the welfare and utility sum decompositions, W(τ) - W(σ) = 2(∑_{v ∈ S} utility(τ, v) - ∑_{v ∈ S} utility(σ, v)) - (E_τ(S, S) - E_σ(S, S)) ≥ 2|S| - |S| = |S| ≥ 1 > 0, so W(τ) > W(σ). The linear arithmetic tactic `omega` detects this contradiction from the established system of bounds.
uses
Finset.card_pos.2have hcard : 1 ≤ S.card := Finset.card_pos.2 hne have hopt' := hopt τ omega
Finset.card_eq_sum_card_fiberwise- The size of a finite set equals the sum of the sizes of its fibers under a map into a target set.
Finset.mem_coe.2- An element belongs to the coercion of a finset if and only if it belongs to the finset.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.filter_filter- Filtering a finset successively by two predicates is equivalent to filtering by their conjunction.
SimpleGraph.card_neighborFinset_eq_degree- The degree of a vertex in a simple graph equals the number of vertices in its neighbor finset.
SimpleGraph.neighborFinset_eq_filter- The neighbor finset of a vertex equals the finset of all vertices in the graph adjacent to it.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finset, then the sum of f over the finset is at most the sum of g.
maxcut_optimal_same_color_le- Under an optimal Max-Cut coloring, a vertex has at least as many neighbors in any given color class as in its own color class.
Finset.sum_const- The sum of a constant value over a finset equals the cardinality of the finset multiplied by the constant.
Finset.card_univ- The cardinality of the universal finset equals the cardinality of the underlying finite type.
Fintype.card_fin- The cardinality of the finite type `Fin n` is n.
smul_eq_mul- Scalar multiplication on natural numbers is standard multiplication.
Nat.mul_le_mul_left- Multiplication on the left by a natural number preserves the order: if n ≤ m then k * n ≤ k * m.
maxcut_welfare_split- The total welfare of a coloring decomposes into the cut edges within S, twice the cut edges between S and the complement of S, and the cut edges within the complement of S.
Finset.sum_congr- If two finsets are equal and the summands agree pointwise on the set, their sums are equal.
Finset.mem_compl.1- An element in the complement of a finset does not belong to the finset.
maxcut_utility_sum_split- The sum of utilities of vertices in S equals the cut edges within S plus the cut edges between S and the complement of S.
Nat.succ_le_of_lt- For natural numbers, n < m implies n + 1 ≤ m.
Finset.sum_add_distrib- A sum of pairwise sums distributes into the sum of the first terms plus the sum of the second terms.
em- The law of excluded middle: for any proposition, either it or its negation is true.
if_pos- An if-then-else expression evaluates to the 'then' branch when the condition is true.
if_neg- An if-then-else expression evaluates to the 'else' branch when the condition is false.
Finset.sum_le_sum_of_subset- Summing a non-negative function over a subset yields at most the sum over the superset.
Finset.subset_univ- Every finset of a finite type is a subset of the universal finset `Finset.univ`.
Finset.card_filter- The cardinality of a filtered finset equals the sum of the indicator values of the filtering predicate.
Finset.card_pos.2- A finset has strictly positive cardinality if and only if it is nonempty.
- The final step delegates the algebraic verification to the `omega` tactic, which checks the inconsistency between the welfare optimality bound and the strict utility improvement directly from the linear equations and inequalities established in preceding steps.
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.
theorem maxcut_optimal_strong_of_degree_le (k : ℕ) (hk : 1 ≤ k) : maxcut_optimal_strong_up_to_degree k (2 * k - 1) := by classical intro V _ G _ hdeg σ hopt S τ hdev obtain ⟨hne, hagree, hgain⟩ := hdev -- at most one neighbour shares each vertex's color have hmono : ∀ v, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1 := by intro v have hsum : (Finset.univ.filter fun w => G.Adj v w).card = ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := by rw [Finset.card_eq_sum_card_fiberwise (f := σ) (t := Finset.univ) (fun _ _ => Finset.mem_coe.2 (Finset.mem_univ _))] simp only [Finset.filter_filter] have hdv : (Finset.univ.filter fun w => G.Adj v w).card ≤ 2 * k - 1 := by have := hdeg v rwa [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter] at this have hlow : ∑ _c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := Finset.sum_le_sum fun c _ => maxcut_optimal_same_color_le G σ hopt v c simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hlow by_contra hc have : k * 2 ≤ k * (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := Nat.mul_le_mul_left k (by omega) omega have hS := maxcut_welfare_split G σ S have hT := maxcut_welfare_split G τ S have hC : ∑ x ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj x w ∧ τ w ≠ τ x then 1 else 0 : ℕ) = ∑ x ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj x w ∧ σ w ≠ σ x then 1 else 0 : ℕ) := by refine Finset.sum_congr rfl fun x hx => Finset.sum_congr rfl fun w hw => ?_ rw [hagree x (Finset.mem_compl.1 hx), hagree w (Finset.mem_compl.1 hw)] have hUS := maxcut_utility_sum_split G σ S have hUT := maxcut_utility_sum_split G τ S have hgains : ∑ v ∈ S, maxcut_utility G σ v + S.card ≤ ∑ v ∈ S, maxcut_utility G τ v := by have := Finset.sum_le_sum fun v hv => Nat.succ_le_of_lt (hgain v hv) simpa [Finset.sum_add_distrib] using this have hpt : ∀ v w, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤ (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := by intro v w rcases em (G.Adj v w ∧ τ w ≠ τ v) with h1 | h1 · rw [if_pos h1] rcases em (σ w = σ v) with h2 | h2 · rw [if_pos (⟨h1.1, h2⟩ : G.Adj v w ∧ σ w = σ v)]; omega · rw [if_pos (⟨h1.1, h2⟩ : G.Adj v w ∧ σ w ≠ σ v)]; omega · rw [if_neg h1]; omega have hA : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤ ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + S.card := by calc ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤ ∑ v ∈ S, (∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + 1) := by refine Finset.sum_le_sum fun v _ => ?_ calc ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤ ∑ w ∈ S, ((if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) := Finset.sum_le_sum fun w _ => hpt v w _ = ∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := Finset.sum_add_distrib _ ≤ _ := by have : ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) ≤ 1 := by calc ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) ≤ ∑ w, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := Finset.sum_le_sum_of_subset (Finset.subset_univ S) _ = (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := (Finset.card_filter _ _).symm _ ≤ 1 := hmono v omega _ = _ := by simp [Finset.sum_add_distrib] have hcard : 1 ≤ S.card := Finset.card_pos.2 hne have hopt' := hopt τ omega