maxcut_defect_two_deviation_welfare_nondecreasing
A strong deviation cannot decrease the cut value when every member of the deviating coalition initially has at most two same-colored neighbors. No Nash assumption or bound outside the coalition is needed.
Statement
theorem maxcut_defect_two_deviation_welfare_nondecreasing {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (C : Finset V) (hdefect : ∀ v ∈ C, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2) (hdev : is_maxcut_strong_deviation G σ C τ) : maxcut_welfare G σ ≤ maxcut_welfare G τ
- Source
- Coalitional cut-change identities are discussed in https://www.mdpi.com/2227-7390/12/4/604 and arXiv:2610.04948.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
- maxcut_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
- maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
- 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 3
- maxcut_one_double_defect_strict_welfareIf a profile has maximum monochromatic degree two and at most one vertex of degree two, every strong deviation strictly increases social…
- maxcut_defect_two_equal_welfare_deviation_structureIf a strong deviation from coalition defect at most two preserves welfare, every deviator has defect two before and one after, every old…
- maxcut_one_double_defect_deviation_decreasesIf a coloring has monochromatic degree at most two with at most one vertex of degree two, every strong deviation stays in that class and…
The proof, explained
The proof decomposes total Max-Cut welfare into internal cut edges within the deviating coalition C, crossing cut edges between C and Cᶜ, and internal cut edges within Cᶜ. Since vertices outside C do not deviate, edges within Cᶜ are unaffected, allowing the welfare change to be expressed as twice the coalition's utility gain minus the increase in internal cut edges in C. By the defect-two assumption, C initially contains at most 2|C| monochromatic directed edges, so the internal cut edges can increase by at most 2|C|. Because each deviating vertex strictly increases its integer utility, the total utility gain is at least |C|, ensuring that the net welfare change is at least 2|C| - 2|C| = 0.
Extract the defining properties of the strong deviation.
From the assumption that C forms a strong deviation from configuration σ to τ, we obtain that C is nonempty, vertices outside C keep their original states (τ v = σ v for v ∉ C), and every member of C strictly increases its Max-Cut utility.
classical obtain ⟨hne, hout, hgain⟩ := hdevThe total utility gain across the deviating coalition is at least the size of the coalition: ∑_{v ∈ C} u_σ(v) + |C| ≤ ∑_{v ∈ C} u_τ(v).
Because utilities are natural numbers, a strict gain u_σ(v) < u_τ(v) implies u_σ(v) + 1 ≤ u_τ(v) via Nat.succ_le_of_lt. Summing over all v ∈ C using Finset.sum_le_sum and distributing the sum with Finset.sum_add_distrib shows that the collective utility increases by at least ∑_{v ∈ C} 1 = |C|.
uses
Nat.succ_le_of_lt,Finset.sum_le_sum,Finset.sum_add_distribhave hgains : ∑ v ∈ C, maxcut_utility G σ v + C.card ≤ ∑ v ∈ C, 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
Decompose the coalitional utility sums and total welfare for σ and τ into internal, crossing, and external edges with respect to C.
For any coloring, maxcut_utility_sum_split decomposes the coalition's utility sum into internal cut edges within C plus crossing cut edges between C and Cᶜ. Similarly, maxcut_welfare_split decomposes total welfare into cut edges within C, twice the crossing cut edges between C and Cᶜ, and cut edges within Cᶜ.
uses
maxcut_utility_sum_split,maxcut_welfare_splithave hu_σ := maxcut_utility_sum_split G σ C have hu_τ := maxcut_utility_sum_split G τ C have hw_σ := maxcut_welfare_split G σ C have hw_τ := maxcut_welfare_split G τ C
The cut edges entirely within Cᶜ are unchanged between σ and τ.
Because vertices outside C do not deviate (τ v = σ v for v ∈ Cᶜ, using Finset.mem_compl), every edge in Cᶜ × Cᶜ has identical endpoint colors under σ and τ. Sum congruence (Finset.sum_congr) shows the sum of cut indicators over Cᶜ × Cᶜ is identical under both colorings.
uses
Finset.sum_congr,Finset.mem_complhave hC : (∑ v ∈ Cᶜ, ∑ w ∈ Cᶜ, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ)) = ∑ v ∈ Cᶜ, ∑ w ∈ Cᶜ, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) := by refine Finset.sum_congr rfl fun v hv => Finset.sum_congr rfl fun w hw => ?_ rw [Finset.mem_compl] at hv hw rw [hout v hv, hout w hw]
For any coloring, the number of monochromatic pairs in C plus the number of cut pairs in C equals the total number of adjacent pairs in C.
For every pair of vertices v, w ∈ C, if they are adjacent, they are either same-colored or differently colored, contributing 1 to exactly one sum and 0 to the other; if they are non-adjacent, both indicators are 0. Summing over all pairs in C × C using Finset.sum_add_distrib and Finset.sum_congr confirms that the sum of monochromatic and cut pairs equals the total number of adjacent pairs in C, independently of the coloring. We record this relation for both σ and τ.
uses
Finset.sum_add_distrib,Finset.sum_congrhave hM (ρ : V → Fin k) : (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ ρ w = ρ v then 1 else 0 : ℕ)) + (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ)) = ∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w then 1 else 0 : ℕ) := by rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun v hv => ?_ rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun w hw => ?_ by_cases h : G.Adj v w · by_cases heq : ρ w = ρ v · simp [h, heq] · simp [h, heq] · simp [h] have hM_σ := hM σ have hM_τ := hM τ
The number of monochromatic pairs in C under σ is at most 2|C|.
For each vertex v ∈ C, its same-colored neighbors within C form a subset of all its same-colored neighbors in G (Finset.card_le_card, Finset.mem_filter, Finset.mem_univ, true_and). By the defect hypothesis, v has at most 2 same-colored neighbors overall. Summing over all v ∈ C with Finset.sum_le_sum and le_trans, and rewriting the sum of indicator variables as set cardinalities using Finset.card_filter, gives an upper bound of ∑_{v ∈ C} 2 = 2|C| by Nat.mul_comm.
uses
Finset.sum_le_sum,Finset.mem_filter,Finset.mem_univ,true_and,le_trans,Finset.card_le_card,Finset.card_filter,Nat.mul_commhave hbound : (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) ≤ 2 * C.card := by calc _ ≤ ∑ v ∈ C, 2 := by apply Finset.sum_le_sum intro v hv have hsub : (C.filter fun w => G.Adj v w ∧ σ w = σ v) ⊆ Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v := by intro w hw simp only [Finset.mem_filter, Finset.mem_univ, true_and] at * exact hw.2 have hh := le_trans (Finset.card_le_card hsub) (hdefect v hv) simpa only [Finset.card_filter] using hh _ = 2 * C.card := by simp [Nat.mul_comm]
Max-Cut welfare under τ is at least that under σ. automation
Total welfare can be written as W(ρ) = 2 ∑_{v ∈ C} u_ρ(v) - E_cut(C, C; ρ) + E_cut(Cᶜ, Cᶜ; ρ). Because edges in Cᶜ are invariant, the welfare change is 2 ΔU - ΔE_cut(C, C). The increase in cut edges within C is bounded by the initial number of monochromatic edges in C (at most 2|C|), while the coalition's aggregate utility gain 2 ΔU is at least 2|C|. The linear integer arithmetic tactic omega combines these relations to conclude maxcut_welfare G σ ≤ maxcut_welfare G τ.
omega
Finset.sum_le_sum- A sum of terms is bounded above by the sum of their pointwise upper bounds.
Nat.succ_le_of_lt- If n < m for natural numbers, then 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.
maxcut_utility_sum_split- The sum of Max-Cut utilities over a vertex set S decomposes into cut edges within S and cut edges between S and Sᶜ.
maxcut_welfare_split- Total Max-Cut welfare decomposes into cut edges within S, twice the cut edges between S and Sᶜ, and cut edges within Sᶜ.
Finset.sum_congr- Two finite sums are equal if their index sets coincide and their summands are equal at every element.
Finset.mem_compl- An element is in the complement of a set if and only if it does not belong to the set.
Finset.mem_filter- An element is in a filtered set if and only if it belongs to the base set and satisfies the filtering condition.
Finset.mem_univ- Every element of a finite type belongs to the universal set Finset.univ.
true_and- The logical conjunction True ∧ p simplifies to p.
le_trans- Inequality is transitive: a ≤ b and b ≤ c imply a ≤ c.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the other's cardinality.
Finset.card_filter- The cardinality of a filtered subset equals the sum over the base set of the indicator of the condition.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
- The final step uses the decision procedure `omega` to close the goal via linear arithmetic over ℕ from the assembled equations and inequalities.
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.
set_option maxHeartbeats 2000000theorem maxcut_defect_two_deviation_welfare_nondecreasing {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (C : Finset V) (hdefect : ∀ v ∈ C, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2) (hdev : is_maxcut_strong_deviation G σ C τ) : maxcut_welfare G σ ≤ maxcut_welfare G τ := by classical obtain ⟨hne, hout, hgain⟩ := hdev have hgains : ∑ v ∈ C, maxcut_utility G σ v + C.card ≤ ∑ v ∈ C, 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 hu_σ := maxcut_utility_sum_split G σ C have hu_τ := maxcut_utility_sum_split G τ C have hw_σ := maxcut_welfare_split G σ C have hw_τ := maxcut_welfare_split G τ C have hC : (∑ v ∈ Cᶜ, ∑ w ∈ Cᶜ, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ)) = ∑ v ∈ Cᶜ, ∑ w ∈ Cᶜ, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) := by refine Finset.sum_congr rfl fun v hv => Finset.sum_congr rfl fun w hw => ?_ rw [Finset.mem_compl] at hv hw rw [hout v hv, hout w hw] have hM (ρ : V → Fin k) : (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ ρ w = ρ v then 1 else 0 : ℕ)) + (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ)) = ∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w then 1 else 0 : ℕ) := by rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun v hv => ?_ rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun w hw => ?_ by_cases h : G.Adj v w · by_cases heq : ρ w = ρ v · simp [h, heq] · simp [h, heq] · simp [h] have hM_σ := hM σ have hM_τ := hM τ have hbound : (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) ≤ 2 * C.card := by calc _ ≤ ∑ v ∈ C, 2 := by apply Finset.sum_le_sum intro v hv have hsub : (C.filter fun w => G.Adj v w ∧ σ w = σ v) ⊆ Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v := by intro w hw simp only [Finset.mem_filter, Finset.mem_univ, true_and] at * exact hw.2 have hh := le_trans (Finset.card_le_card hsub) (hdefect v hv) simpa only [Finset.card_filter] using hh _ = 2 * C.card := by simp [Nat.mul_comm] omega