maxcut_optimal_no_clique_deviation
In the unweighted Max-k-Cut game on a finite simple graph, no coalition that induces a clique has a strong deviation from a welfare-optimal coloring.
Statement
theorem maxcut_optimal_no_clique_deviation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (hopt : is_maxcut_optimal G σ) (S : Finset V) (hclique : G.IsClique (S : Set V)) (τ : V → Fin k) : ¬ is_maxcut_strong_deviation G σ S τ
- Formalizes
- arXiv:2610.04948
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
- 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_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_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)…
- 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_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.
Read back from the Lean
For any finite type V, any simple graph G on V with decidable adjacency, any natural number k, any partition/coloring σ : V → Fin k, any finite subset S : Finset V, and any partition/coloring τ : V → Fin k:
If:
1. σ is max-cut optimal, meaning that for all τ' : V → Fin k, the total welfare under τ' is at most that under σ (where welfare is the sum over all vertices v : V of the cut utility of v, i.e., the number of neighbors w of v such that the colors differ); and
2. S induces a clique in G (every pair of distinct vertices in S are adjacent in G);
Then τ is not a strong deviation from σ on S, meaning it is not the case that:
- S is non-empty,
- τ v = σ v for all v ∉ S, and
- every vertex v ∈ S strictly increases its cut utility under τ compared to σ (i.e., maxcut_utility G σ v < maxcut_utility G τ v).
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
A strong deviation on a clique would require fiber sizes to shrink, forcing equality of cut counts within the clique, which makes welfare strictly increase and contradicts optimality.
monochromatic neighbors strictly decrease
utility plus monochromatic degree is degree, and optimality gives an inequality
uses
maxcut_utility_add_monochromatic_card,maxcut_optimal_same_color_lehave huσ := maxcut_utility_add_monochromatic_card G σ v have huτ := maxcut_utility_add_monochromatic_card G τ v have hopt_v := maxcut_optimal_same_color_le G σ hopt v (τ v) have hlt : (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card < (Finset.univ.filter fun w => G.Adj v w ∧ σ w = τ v).card := by omega
neighbors in S strictly decrease
split into S and S complement, where tau and sigma agree
uses
Finset.card_filter,Finset.sum_add_sum_compl,Finset.filter_congr,Finset.mem_complhave h_split (p : V → Prop) [DecidablePred p] : (Finset.univ.filter p).card = (S.filter p).card + (Sᶜ.filter p).card := by simp only [Finset.card_filter] exact (Finset.sum_add_sum_compl S _).symm have h_split_τ := h_split (fun w => G.Adj v w ∧ τ w = τ v) have h_split_σ := h_split (fun w => G.Adj v w ∧ σ w = τ v) have h_compl_eq : (Sᶜ.filter fun w => G.Adj v w ∧ τ w = τ v).card = (Sᶜ.filter fun w => G.Adj v w ∧ σ w = τ v).card := by congr 1 refine Finset.filter_congr fun w hw => ?_ rw [Finset.mem_compl] at hw rw [hagree w hw] rw [h_split_τ, h_split_σ, h_compl_eq] at hlt omega
tau fiber card on clique
all other vertices in clique are adjacent
uses
Finset.mem_filter,Finset.mem_insert,eq_or_ne,Finset.card_insert_of_notMemhave h_eq : (S.filter fun w => τ w = τ v) = insert v (S.filter fun w => G.Adj v w ∧ τ w = τ v) := by ext w simp only [Finset.mem_filter, Finset.mem_insert] constructor · rintro ⟨hw, hcol⟩ rcases eq_or_ne w v with rfl | hne · left; rfl · right refine ⟨hw, ?_, hcol⟩ exact G.adj_symm (hclique (Finset.mem_coe.2 hw) (Finset.mem_coe.2 hv) hne) · rintro (rfl | ⟨hw, _, hcol⟩) · exact ⟨hv, rfl⟩ · exact ⟨hw, hcol⟩ have hv_not_mem : v ∉ S.filter fun w => G.Adj v w ∧ τ w = τ v := by simp rw [h_eq, Finset.card_insert_of_notMem hv_not_mem]
sigma fiber card le
subset card le
uses
Finset.card_le_card,Finset.mem_filterrefine Finset.card_le_card fun w hw => ?_ simp only [Finset.mem_filter] at hw ⊢ exact ⟨hw.1, hw.2.2⟩
fiber eq from le and sum eq
strict sum contradiction
uses
Nat.lt_of_le_of_ne,Finset.sum_lt_sum,Finset.mem_univby_contra hc have hlt : f c < g c := Nat.lt_of_le_of_ne (hle c) hc have : ∑ x, f x < ∑ x, g x := Finset.sum_lt_sum (fun x _ => hle x) ⟨c, Finset.mem_univ c, hlt⟩ omega
adjacency redundant in clique
every pair in clique is adjacent
uses
Finset.sum_congr,eq_or_nehave h_simp (ρ : V → Fin k) : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) = ∑ c : Fin k, (S.filter fun v => ρ v = c).card * (S.card - (S.filter fun w => ρ w = c).card) := by have h1 : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) = ∑ v ∈ S, ∑ w ∈ S, (if ρ w ≠ ρ v then 1 else 0 : ℕ) := by refine Finset.sum_congr rfl fun v hv => Finset.sum_congr rfl fun w hw => ?_ rcases eq_or_ne w v with rfl | hne · simp · have : G.Adj v w := G.adj_symm (hclique (Finset.mem_coe.2 hw) (Finset.mem_coe.2 hv) hne) simp [this] rw [h1]
inner count is card minus fiber card
filter and filter not partition S
uses
Finset.card_filter,Finset.card_filter_add_card_filter_not,Finset.sum_congrhave h2 : ∀ v ∈ S, ∑ w ∈ S, (if ρ w ≠ ρ v then 1 else 0 : ℕ) = S.card - (S.filter fun w => ρ w = ρ v).card := by intro v _ rw [← Finset.card_filter] have hnot := Finset.card_filter_add_card_filter_not (s := S) (p := fun w => ρ w = ρ v) change (S.filter fun w => ρ w = ρ v).card + (S.filter fun w => ρ w ≠ ρ v).card = S.card at hnot omega have h3 : ∑ v ∈ S, ∑ w ∈ S, (if ρ w ≠ ρ v then 1 else 0 : ℕ) = ∑ v ∈ S, (fun v => S.card - (S.filter fun w => ρ w = ρ v).card) v := by exact Finset.sum_congr rfl h2 rw [h3]
internal cut determined by fiber cards
fiberwise sum
uses
Finset.sum_fiberwise_of_maps_to,Finset.mem_univ,Finset.sum_congr,Finset.mem_filter,Finset.sum_const,smul_eq_mulhave h4 := Finset.sum_fiberwise_of_maps_to (g := ρ) (s := S) (t := Finset.univ) (fun _ _ => Finset.mem_univ _) (fun v => S.card - (S.filter fun w => ρ w = ρ v).card) rw [← h4] refine Finset.sum_congr rfl fun c _ => ?_ have hconst : ∀ v ∈ S.filter fun v => ρ v = c, (S.card - (S.filter fun w => ρ w = ρ v).card) = (S.card - (S.filter fun w => ρ w = c).card) := by intro v hv simp only [Finset.mem_filter] at hv rw [hv.2] rw [Finset.sum_congr rfl hconst, Finset.sum_const, smul_eq_mul] rw [h_simp τ, h_simp σ] refine Finset.sum_congr rfl fun c _ => ?_ rw [hfiber c]
assume strong deviation
S is nonempty, tau agrees with sigma on S complement, and every vertex in S gains
classical intro hdev obtain ⟨hne, hagree, hgain⟩ := hdev
tau fiber card le sigma fiber card on S
empty or use mono cancel, tau fiber, and sigma fiber le
uses
Finset.eq_empty_or_nonempty,Finset.card_empty,Finset.mem_filter,maxcut_optimal_no_clique_deviation_mono_cancel,maxcut_optimal_no_clique_deviation_clique_tau_fiber,maxcut_optimal_no_clique_deviation_clique_sigma_fiber_lehave hle : ∀ c : Fin k, (S.filter fun w => τ w = c).card ≤ (S.filter fun w => σ w = c).card := by intro c rcases (S.filter fun w => τ w = c).eq_empty_or_nonempty with he | ⟨v, hv⟩ · rw [he, Finset.card_empty]; omega · simp only [Finset.mem_filter] at hv have h1 := maxcut_optimal_no_clique_deviation_mono_cancel G σ τ hopt S hagree v (hgain v hv.1) have h2 := maxcut_optimal_no_clique_deviation_clique_tau_fiber G S hclique τ v hv.1 have h3 := maxcut_optimal_no_clique_deviation_clique_sigma_fiber_le G S σ v (τ v) rw [hv.2] at h1 h2 h3 omega
fiber cards equal
sum of fiber cards is card of S
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univ,maxcut_optimal_no_clique_deviation_fiber_eq_of_le_and_sum_eqhave hsum_τ : ∑ c : Fin k, (S.filter fun w => τ w = c).card = S.card := by have := Finset.card_eq_sum_card_fiberwise (s := S) (t := Finset.univ) (f := τ) (fun _ _ => Finset.mem_univ _) rw [← this] have hsum_σ : ∑ c : Fin k, (S.filter fun w => σ w = c).card = S.card := by have := Finset.card_eq_sum_card_fiberwise (s := S) (t := Finset.univ) (f := σ) (fun _ _ => Finset.mem_univ _) rw [← this] have hsum_eq : ∑ c : Fin k, (S.filter fun w => τ w = c).card = ∑ c : Fin k, (S.filter fun w => σ w = c).card := by rw [hsum_τ, hsum_σ] have hfiber : ∀ c : Fin k, (S.filter fun w => τ w = c).card = (S.filter fun w => σ w = c).card := fun c => maxcut_optimal_no_clique_deviation_fiber_eq_of_le_and_sum_eq _ _ hle hsum_eq c
internal and complement cut equal
clique cut eq and agreement on complement
uses
maxcut_optimal_no_clique_deviation_A_clique_eq,maxcut_welfare_split,Finset.sum_congrhave hA_eq := maxcut_optimal_no_clique_deviation_A_clique_eq G S hclique σ τ hfiber 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)]
welfare contradiction
welfare split and utility sum split imply welfare increases, contradicting optimality
uses
maxcut_utility_sum_split,Finset.sum_le_sum,Nat.succ_le_of_lt,Finset.sum_add_distrib,Finset.card_pos.2have 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 hcard : 1 ≤ S.card := Finset.card_pos.2 hne have hopt' := hopt τ omega
maxcut_utility_add_monochromatic_card- utility plus monochromatic degree equals degree
maxcut_optimal_same_color_le- optimality implies monochromatic neighbors do not exceed any other color
Finset.card_filter- cardinality as sum of indicator
Finset.sum_add_sum_compl- sum over S plus sum over complement is sum over univ
Finset.filter_congr- filter with equivalent predicates are equal
Finset.mem_compl- membership in complement
Finset.mem_filter- membership in filter
Finset.mem_insert- membership in insert
eq_or_ne- equality or inequality
Finset.card_insert_of_notMem- inserting a non-member increases card by 1
Finset.card_le_card- subset card le
Nat.lt_of_le_of_ne- le and ne implies lt
Finset.sum_lt_sum- strict sum inequality
Finset.mem_univ- univ mem
Finset.sum_congr- congruence for sums
Finset.card_filter_add_card_filter_not- sum of filter and not filter is card
Finset.sum_fiberwise_of_maps_to- fiberwise sum
Finset.sum_const- sum of constant
smul_eq_mul- smul is mul
Finset.eq_empty_or_nonempty- empty or nonempty
Finset.card_empty- card of empty is 0
maxcut_optimal_no_clique_deviation_mono_cancel- monochromatic cancellation
maxcut_optimal_no_clique_deviation_clique_tau_fiber- clique tau fiber
maxcut_optimal_no_clique_deviation_clique_sigma_fiber_le- sigma fiber le
Finset.card_eq_sum_card_fiberwise- card eq fiberwise
maxcut_optimal_no_clique_deviation_fiber_eq_of_le_and_sum_eq- fiber eq from le and sum eq
maxcut_optimal_no_clique_deviation_A_clique_eq- clique cut eq
maxcut_welfare_split- welfare split
maxcut_utility_sum_split- utility sum split
Finset.sum_le_sum- sum le sum
Nat.succ_le_of_lt- succ le of lt
Finset.sum_add_distrib- sum add distrib
Finset.card_pos.2- pos card
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 BigOperatorstheorem maxcut_optimal_no_clique_deviation_mono_cancel {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (hopt : is_maxcut_optimal G σ) (S : Finset V) (hagree : ∀ v ∉ S, τ v = σ v) (v : V) (hgain : maxcut_utility G σ v < maxcut_utility G τ v) : (S.filter fun w => G.Adj v w ∧ τ w = τ v).card < (S.filter fun w => G.Adj v w ∧ σ w = τ v).card := by have huσ := maxcut_utility_add_monochromatic_card G σ v have huτ := maxcut_utility_add_monochromatic_card G τ v have hopt_v := maxcut_optimal_same_color_le G σ hopt v (τ v) have hlt : (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card < (Finset.univ.filter fun w => G.Adj v w ∧ σ w = τ v).card := by omega have h_split (p : V → Prop) [DecidablePred p] : (Finset.univ.filter p).card = (S.filter p).card + (Sᶜ.filter p).card := by simp only [Finset.card_filter] exact (Finset.sum_add_sum_compl S _).symm have h_split_τ := h_split (fun w => G.Adj v w ∧ τ w = τ v) have h_split_σ := h_split (fun w => G.Adj v w ∧ σ w = τ v) have h_compl_eq : (Sᶜ.filter fun w => G.Adj v w ∧ τ w = τ v).card = (Sᶜ.filter fun w => G.Adj v w ∧ σ w = τ v).card := by congr 1 refine Finset.filter_congr fun w hw => ?_ rw [Finset.mem_compl] at hw rw [hagree w hw] rw [h_split_τ, h_split_σ, h_compl_eq] at hlt omegatheorem maxcut_optimal_no_clique_deviation_clique_tau_fiber {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) (hclique : G.IsClique (S : Set V)) {k : ℕ} (τ : V → Fin k) (v : V) (hv : v ∈ S) : (S.filter fun w => τ w = τ v).card = (S.filter fun w => G.Adj v w ∧ τ w = τ v).card + 1 := by have h_eq : (S.filter fun w => τ w = τ v) = insert v (S.filter fun w => G.Adj v w ∧ τ w = τ v) := by ext w simp only [Finset.mem_filter, Finset.mem_insert] constructor · rintro ⟨hw, hcol⟩ rcases eq_or_ne w v with rfl | hne · left; rfl · right refine ⟨hw, ?_, hcol⟩ exact G.adj_symm (hclique (Finset.mem_coe.2 hw) (Finset.mem_coe.2 hv) hne) · rintro (rfl | ⟨hw, _, hcol⟩) · exact ⟨hv, rfl⟩ · exact ⟨hw, hcol⟩ have hv_not_mem : v ∉ S.filter fun w => G.Adj v w ∧ τ w = τ v := by simp rw [h_eq, Finset.card_insert_of_notMem hv_not_mem]theorem maxcut_optimal_no_clique_deviation_clique_sigma_fiber_le {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) {k : ℕ} (σ : V → Fin k) (v : V) (c : Fin k) : (S.filter fun w => G.Adj v w ∧ σ w = c).card ≤ (S.filter fun w => σ w = c).card := by refine Finset.card_le_card fun w hw => ?_ simp only [Finset.mem_filter] at hw ⊢ exact ⟨hw.1, hw.2.2⟩theorem maxcut_optimal_no_clique_deviation_fiber_eq_of_le_and_sum_eq {k : ℕ} (f g : Fin k → ℕ) (hle : ∀ c, f c ≤ g c) (hsum : ∑ c, f c = ∑ c, g c) (c : Fin k) : f c = g c := by by_contra hc have hlt : f c < g c := Nat.lt_of_le_of_ne (hle c) hc have : ∑ x, f x < ∑ x, g x := Finset.sum_lt_sum (fun x _ => hle x) ⟨c, Finset.mem_univ c, hlt⟩ omegatheorem maxcut_optimal_no_clique_deviation_A_clique_eq {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) (hclique : G.IsClique (S : Set V)) {k : ℕ} (σ τ : V → Fin k) (hfiber : ∀ c : Fin k, (S.filter fun w => τ w = c).card = (S.filter fun w => σ w = c).card) : ∑ 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 : ℕ) := by have h_simp (ρ : V → Fin k) : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) = ∑ c : Fin k, (S.filter fun v => ρ v = c).card * (S.card - (S.filter fun w => ρ w = c).card) := by have h1 : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) = ∑ v ∈ S, ∑ w ∈ S, (if ρ w ≠ ρ v then 1 else 0 : ℕ) := by refine Finset.sum_congr rfl fun v hv => Finset.sum_congr rfl fun w hw => ?_ rcases eq_or_ne w v with rfl | hne · simp · have : G.Adj v w := G.adj_symm (hclique (Finset.mem_coe.2 hw) (Finset.mem_coe.2 hv) hne) simp [this] rw [h1] have h2 : ∀ v ∈ S, ∑ w ∈ S, (if ρ w ≠ ρ v then 1 else 0 : ℕ) = S.card - (S.filter fun w => ρ w = ρ v).card := by intro v _ rw [← Finset.card_filter] have hnot := Finset.card_filter_add_card_filter_not (s := S) (p := fun w => ρ w = ρ v) change (S.filter fun w => ρ w = ρ v).card + (S.filter fun w => ρ w ≠ ρ v).card = S.card at hnot omega have h3 : ∑ v ∈ S, ∑ w ∈ S, (if ρ w ≠ ρ v then 1 else 0 : ℕ) = ∑ v ∈ S, (fun v => S.card - (S.filter fun w => ρ w = ρ v).card) v := by exact Finset.sum_congr rfl h2 rw [h3] have h4 := Finset.sum_fiberwise_of_maps_to (g := ρ) (s := S) (t := Finset.univ) (fun _ _ => Finset.mem_univ _) (fun v => S.card - (S.filter fun w => ρ w = ρ v).card) rw [← h4] refine Finset.sum_congr rfl fun c _ => ?_ have hconst : ∀ v ∈ S.filter fun v => ρ v = c, (S.card - (S.filter fun w => ρ w = ρ v).card) = (S.card - (S.filter fun w => ρ w = c).card) := by intro v hv simp only [Finset.mem_filter] at hv rw [hv.2] rw [Finset.sum_congr rfl hconst, Finset.sum_const, smul_eq_mul] rw [h_simp τ, h_simp σ] refine Finset.sum_congr rfl fun c _ => ?_ rw [hfiber c]/-- Every welfare-optimal coloring in the Max-k-Cut game resists strong deviations by clique coalitions. -/theorem maxcut_optimal_no_clique_deviation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (hopt : is_maxcut_optimal G σ) (S : Finset V) (hclique : G.IsClique (S : Set V)) (τ : V → Fin k) : ¬ is_maxcut_strong_deviation G σ S τ := by classical intro hdev obtain ⟨hne, hagree, hgain⟩ := hdev have hle : ∀ c : Fin k, (S.filter fun w => τ w = c).card ≤ (S.filter fun w => σ w = c).card := by intro c rcases (S.filter fun w => τ w = c).eq_empty_or_nonempty with he | ⟨v, hv⟩ · rw [he, Finset.card_empty]; omega · simp only [Finset.mem_filter] at hv have h1 := maxcut_optimal_no_clique_deviation_mono_cancel G σ τ hopt S hagree v (hgain v hv.1) have h2 := maxcut_optimal_no_clique_deviation_clique_tau_fiber G S hclique τ v hv.1 have h3 := maxcut_optimal_no_clique_deviation_clique_sigma_fiber_le G S σ v (τ v) rw [hv.2] at h1 h2 h3 omega have hsum_τ : ∑ c : Fin k, (S.filter fun w => τ w = c).card = S.card := by have := Finset.card_eq_sum_card_fiberwise (s := S) (t := Finset.univ) (f := τ) (fun _ _ => Finset.mem_univ _) rw [← this] have hsum_σ : ∑ c : Fin k, (S.filter fun w => σ w = c).card = S.card := by have := Finset.card_eq_sum_card_fiberwise (s := S) (t := Finset.univ) (f := σ) (fun _ _ => Finset.mem_univ _) rw [← this] have hsum_eq : ∑ c : Fin k, (S.filter fun w => τ w = c).card = ∑ c : Fin k, (S.filter fun w => σ w = c).card := by rw [hsum_τ, hsum_σ] have hfiber : ∀ c : Fin k, (S.filter fun w => τ w = c).card = (S.filter fun w => σ w = c).card := fun c => maxcut_optimal_no_clique_deviation_fiber_eq_of_le_and_sum_eq _ _ hle hsum_eq c have hA_eq := maxcut_optimal_no_clique_deviation_A_clique_eq G S hclique σ τ hfiber 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 hcard : 1 ≤ S.card := Finset.card_pos.2 hne have hopt' := hopt τ omega