AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_no_clique_deviation

theoremverifiedformalization

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.

  1. monochromatic neighbors strictly decrease

    utility plus monochromatic degree is degree, and optimality gives an inequality

    lines 10–14

    uses maxcut_utility_add_monochromatic_card, maxcut_optimal_same_color_le

      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
  2. neighbors in S strictly decrease

    split into S and S complement, where tau and sigma agree

    lines 15–28

    uses Finset.card_filter, Finset.sum_add_sum_compl, Finset.filter_congr, Finset.mem_compl

      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
      omega
  3. tau fiber card on clique

    all other vertices in clique are adjacent

    lines 35–50

    uses Finset.mem_filter, Finset.mem_insert, eq_or_ne, Finset.card_insert_of_notMem

      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]
  4. sigma fiber card le

    subset card le

    lines 57–59

    uses Finset.card_le_card, Finset.mem_filter

      refine Finset.card_le_card fun w hw => ?_
      simp only [Finset.mem_filter] at hw ⊢
      exact ⟨hw.1, hw.2.2⟩
  5. fiber eq from le and sum eq

    strict sum contradiction

    lines 64–68

    uses Nat.lt_of_le_of_ne, Finset.sum_lt_sum, Finset.mem_univ

      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⟩
      omega
  6. adjacency redundant in clique

    every pair in clique is adjacent

    lines 76–86

    uses Finset.sum_congr, eq_or_ne

      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]
  7. inner count is card minus fiber card

    filter and filter not partition S

    lines 87–97

    uses Finset.card_filter, Finset.card_filter_add_card_filter_not, Finset.sum_congr

        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]
  8. internal cut determined by fiber cards

    fiberwise sum

    lines 98–111

    uses Finset.sum_fiberwise_of_maps_to, Finset.mem_univ, Finset.sum_congr, Finset.mem_filter, Finset.sum_const, smul_eq_mul

        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]
  9. assume strong deviation

    S is nonempty, tau agrees with sigma on S complement, and every vertex in S gains

    lines 118–120

      classical
      intro hdev
      obtain ⟨hne, hagree, hgain⟩ := hdev
  10. tau fiber card le sigma fiber card on S

    empty or use mono cancel, tau fiber, and sigma fiber le

    lines 121–130

    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_le

      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
  11. fiber cards equal

    sum of fiber cards is card of S

    lines 131–143

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ, maxcut_optimal_no_clique_deviation_fiber_eq_of_le_and_sum_eq

      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
  12. internal and complement cut equal

    clique cut eq and agreement on complement

    lines 144–150

    uses maxcut_optimal_no_clique_deviation_A_clique_eq, maxcut_welfare_split, Finset.sum_congr

      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)]
  13. welfare contradiction

    welfare split and utility sum split imply welfare increases, contradicting optimality

    lines 151–158

    uses maxcut_utility_sum_split, Finset.sum_le_sum, Nat.succ_le_of_lt, Finset.sum_add_distrib, Finset.card_pos.2

      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
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

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
See it in the graphDiscuss this resultChallenge it