maxcut_optimal_same_color_le
At 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 most the number of neighbours with color c (optimal colorings are Nash equilibria).
Statement
theorem maxcut_optimal_same_color_le {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (hopt : is_maxcut_optimal G σ) (v : V) (c : Fin k) : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card
- Source
- step towards maxcut_optimal_strong_of_degree_le (arXiv:2610.04948, Corollary 9)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
- 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 8
- maxcut_op89_exists_of_card_le_two_mul_add_oneFor every integer k ≥ 3 and every finite simple graph G on at most 2k+1 vertices, the unweighted Max-k-Cut game on (G,k) admits an optimal…
- maxcut_optimal_no_clique_deviationIn the unweighted Max-k-Cut game on a finite simple graph, no coalition that induces a clique has a strong deviation from a…
- maxcut_complete_graph_optimal_balancedIn an optimal k-colouring of the complete graph K_n, any two colour classes differ in size by at most one: a vertex whose class has a…
- maxcut_optimal_strong_of_color_unusedIf σ is an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and some colour c is never used by σ, then σ is a…
- maxcut_optimal_strong_of_degree_leFor 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…
- maxcut_deviation_degree_sum_geLet σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then…
- maxcut_deviation_internal_color_count_ltLet σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then…
- maxcut_anchor_three_initial_optimalThe displayed initial coloring sigma of the 91-vertex graph G_3 in arXiv:2610.04948 maximizes social welfare among all three-colorings.
The proof, explained
The proof evaluates the local optimality of σ by comparing it to the coloring τ obtained by recoloring vertex v to c while leaving all other vertices unchanged. Because all edges disjoint from v are unaffected by this change, the change in social welfare is determined entirely by the change in the utility of v, meaning that optimality of σ forces the utility of v under τ to be at most its utility under σ. Expressing utility as the total degree of v minus the number of neighbors sharing the vertex's color translates this utility inequality into the required bound: v has at most as many neighbors of color σ(v) as it has of color c.
Let τ be the coloring obtained from σ by recoloring vertex v with color c, leaving all other vertices unchanged.
We introduce the coloring τ = Function.update(σ, v, c), which agrees with σ on every vertex except possibly v, where its value is set to c.
classical set τ := Function.update σ v c with hτ
The cut edges strictly within V \ {v} contribute identically to welfare under σ and under τ.
Decomposing social welfare around the singleton {v} using `maxcut_welfare_split`, the edges with both endpoints in {v}ᶜ do not involve v. By `Function.update_of_ne`, τ and σ agree on all vertices in {v}ᶜ, so the summands for edges within {v}ᶜ are identical. Applying `Finset.sum_congr` shows that this term is identical under σ and τ.
uses
maxcut_welfare_split,Finset.sum_congr,Function.update_of_nehave hS := maxcut_welfare_split G σ {v} have hT := maxcut_welfare_split G τ {v} have hC : ∑ x ∈ ({v} : Finset V)ᶜ, ∑ w ∈ ({v} : Finset V)ᶜ, (if G.Adj x w ∧ τ w ≠ τ x then 1 else 0 : ℕ) = ∑ x ∈ ({v} : Finset V)ᶜ, ∑ w ∈ ({v} : Finset V)ᶜ, (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 => ?_ have hx' : x ≠ v := by simpa using hx have hw' : w ≠ v := by simpa using hw simp [hτ, Function.update_of_ne hx', Function.update_of_ne hw']
For both σ and τ, the social welfare simplifies to twice the utility of v plus the unaffected cut edges within V \ {v}.
By `maxcut_utility_sum_split`, the utility of v is the sum of cut edges within {v} and cut edges between {v} and {v}ᶜ. Since simple graphs have no self-loops (`SimpleGraph.irrefl`), edges within {v} evaluate to 0 (`false_and`, `if_false`). Simplifying the singleton sums with `Finset.sum_singleton` reveals that the welfare under both σ and τ equals 2 * maxcut_utility(v) plus the cut edges within {v}ᶜ.
uses
maxcut_utility_sum_split,Finset.sum_singleton,SimpleGraph.irrefl,false_and,if_falsehave hUS := maxcut_utility_sum_split G σ {v} have hUT := maxcut_utility_sum_split G τ {v} simp only [Finset.sum_singleton, SimpleGraph.irrefl, false_and, if_false] at hS hT hUS hUT
The utility of v under τ is at most its utility under σ.
Since σ maximizes welfare (`hopt`), the welfare under τ is at most that under σ. Because the edges strictly within {v}ᶜ contribute the same amount to both welfares, the inequality reduces to 2 * maxcut_utility(τ, v) ≤ 2 * maxcut_utility(σ, v), which linear arithmetic (`omega`) simplifies to maxcut_utility(τ, v) ≤ maxcut_utility(σ, v).
have hle : maxcut_utility G τ v ≤ maxcut_utility G σ v := by have := hopt τ; omega
The utility of v under τ equals the number of neighbors of v whose color under σ is not c.
By definition, the utility of v under τ counts neighbors w of v with τ(w) ≠ τ(v). Since τ(v) = c, and for any neighbor w ≠ v we have τ(w) = σ(w) by `Function.update_of_ne`, the condition τ(w) ≠ τ(v) is equivalent to σ(w) ≠ c (and w = v is excluded because G has no self-loops). Applying `Finset.filter_congr` equates the sets and their cardinalities.
uses
Finset.filter_congr,Function.update_of_nehave hτu : maxcut_utility G τ v = (Finset.univ.filter fun w => G.Adj v w ∧ σ w ≠ c).card := by unfold maxcut_utility congr 1 refine Finset.filter_congr fun w _ => ?_ by_cases hw : w = v · subst hw; simp · simp [hτ, Function.update_of_ne hw]
The neighbors of v partition into those with color σ(v) (respectively c) and those without, summing to the degree of v.
By `Finset.card_filter_add_card_filter_not`, the neighbors of v with color σ(v) plus those with color different from σ(v) equal the total degree of v. The same partitioning holds for color c. Simplifying the nested filters with `Finset.filter_filter` puts both equations in terms of conjunctions on the neighborhood of v.
uses
Finset.card_filter_add_card_filter_not,Finset.filter_filterhave h1 := Finset.card_filter_add_card_filter_not (s := Finset.univ.filter fun w => G.Adj v w) (fun w => σ w = σ v) have h2 := Finset.card_filter_add_card_filter_not (s := Finset.univ.filter fun w => G.Adj v w) (fun w => σ w = c) simp only [Finset.filter_filter] at h1 h2
The number of neighbors of v with color σ(v) is at most the number of neighbors with color c.
Substituting the formula for the utility under τ into the utility inequality shows that the number of neighbors with color different from c is at most the number of neighbors with color different from σ(v). Since the total number of neighbors is identical in both partitions, subtracting from the degree shows that the number of neighbors sharing color σ(v) is at most the number of neighbors sharing color c; linear arithmetic (`omega`) after rewriting inequalities with `ne_eq` completes the deduction.
uses
ne_eqrw [hτu] at hle unfold maxcut_utility at hle simp only [ne_eq] at hle h1 h2 omega
maxcut_welfare_split- The total cut welfare of a coloring decomposes into cut edges within a subset S, twice the cut edges between S and its complement, and cut edges within the complement.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Function.update_of_ne- Updating a function at a point a' does not alter its value at any distinct point a ≠ a'.
maxcut_utility_sum_split- The sum of utilities over a subset S equals the cut edges within S plus the cut edges between S and its complement.
Finset.sum_singleton- The sum of a function over a singleton set {a} is the value of the function at a.
SimpleGraph.irrefl- In a simple graph, no vertex is adjacent to itself (no self-loops).
false_and- The conjunction of False with any proposition is False.
if_false- An if-then-else expression whose condition is False simplifies to the else branch.
Finset.filter_congr- Filtering a finite set by two predicates produces the same set if the predicates are logically equivalent on all elements of the set.
Finset.card_filter_add_card_filter_not- The number of elements in a finite set satisfying a predicate plus the number not satisfying it equals the cardinality of the set.
Finset.filter_filter- Filtering a finite set successively by two predicates is equivalent to filtering once by their conjunction.
ne_eq- The inequality a ≠ b is definitionally identical to the negation ¬(a = b).
- The tactic `omega` is used in steps 4 and 7 to resolve linear arithmetic over ℕ: first to deduce the utility inequality from welfare optimality once unaffected edges cancel, and later to deduce the inequality on same-color neighbors by subtracting non-matching neighbors from the total 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.
theorem maxcut_optimal_same_color_le {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (hopt : is_maxcut_optimal G σ) (v : V) (c : Fin k) : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := by classical set τ := Function.update σ v c with hτ have hS := maxcut_welfare_split G σ {v} have hT := maxcut_welfare_split G τ {v} have hC : ∑ x ∈ ({v} : Finset V)ᶜ, ∑ w ∈ ({v} : Finset V)ᶜ, (if G.Adj x w ∧ τ w ≠ τ x then 1 else 0 : ℕ) = ∑ x ∈ ({v} : Finset V)ᶜ, ∑ w ∈ ({v} : Finset V)ᶜ, (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 => ?_ have hx' : x ≠ v := by simpa using hx have hw' : w ≠ v := by simpa using hw simp [hτ, Function.update_of_ne hx', Function.update_of_ne hw'] have hUS := maxcut_utility_sum_split G σ {v} have hUT := maxcut_utility_sum_split G τ {v} simp only [Finset.sum_singleton, SimpleGraph.irrefl, false_and, if_false] at hS hT hUS hUT have hle : maxcut_utility G τ v ≤ maxcut_utility G σ v := by have := hopt τ; omega have hτu : maxcut_utility G τ v = (Finset.univ.filter fun w => G.Adj v w ∧ σ w ≠ c).card := by unfold maxcut_utility congr 1 refine Finset.filter_congr fun w _ => ?_ by_cases hw : w = v · subst hw; simp · simp [hτ, Function.update_of_ne hw] have h1 := Finset.card_filter_add_card_filter_not (s := Finset.univ.filter fun w => G.Adj v w) (fun w => σ w = σ v) have h2 := Finset.card_filter_add_card_filter_not (s := Finset.univ.filter fun w => G.Adj v w) (fun w => σ w = c) simp only [Finset.filter_filter] at h1 h2 rw [hτu] at hle unfold maxcut_utility at hle simp only [ne_eq] at hle h1 h2 omega