AFTD Auto-Formalizing Theoretical Domains

maxcut_defect_two_equal_welfare_deviation_structure

theoremverified

If a strong deviation from coalition defect at most two preserves welfare, every deviator has defect two before and one after, every old monochromatic edge touching the coalition is internal, and every new monochromatic edge touching it is a boundary edge.

Statement

theorem maxcut_defect_two_equal_welfare_deviation_structure
    {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 τ)
    (heq : maxcut_welfare G σ = maxcut_welfare G τ) :
    (∀ v ∈ C, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 ∧
      (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card = 1) ∧
    (∀ v ∈ C, ∀ w, G.Adj v w → σ v = σ w → w ∈ C) ∧
    (∀ v ∈ C, ∀ w ∈ C, G.Adj v w → τ v ≠ τ w)
Source
Equality case of the coalition incidence-count argument.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • maxcut_defect_two_deviation_welfare_nondecreasingA strong deviation cannot decrease the cut value when every member of the deviating coalition initially has at most two same-colored…
  • 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_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_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_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
  • 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_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.
Used by 2

The proof, explained

The proof decomposes the total welfare and coalition utilities into internal cut edges, boundary edges, and complement edges before and after deviation. Because each deviator strictly gains utility while welfare is preserved and external edges remain unchanged, the linear relationship between welfare and cuts forces the aggregate utility gain to equal |C|, all 2|C| initial monochromatic half-edges to lie strictly inside C, and no monochromatic edges to remain internal after deviation. Averaging then implies that every deviator begins with defect 2 and ends with defect 1, old monochromatic edges cannot cross the coalition boundary, and new monochromatic edges touching C must be boundary edges.

  1. The aggregate utility gain of the coalition C is at least |C|

    Unpack the strong deviation hypothesis into non-emptiness of C, constancy of colors outside C, and strict utility gain for each v ∈ C. Since each deviator strictly increases its integer utility, its gain is at least 1; summing over C yields ∑_{v ∈ C} u_σ(v) + |C| ≤ ∑_{v ∈ C} u_τ(v).

    lines 13–18

    uses Finset.sum_le_sum, Nat.succ_le_of_lt, Finset.sum_add_distrib

      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
  2. Welfare and utility sums decompose into internal, boundary, and external cuts, with external cuts unaffected by the deviation

    Express the utility sum on C and total welfare for both σ and τ using decomposition lemmas that split edges into those internal to C, crossing between C and Cᶜ, and internal to Cᶜ. Since no vertex outside C changes its color under deviation, the cut edges entirely within Cᶜ remain identical between σ and τ.

    lines 19–27

    uses maxcut_utility_sum_split, maxcut_welfare_split, Finset.sum_congr, Finset.mem_compl

      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]
  3. For any coloring, the number of directed monochromatic pairs in C plus cut pairs in C equals the total adjacent pairs in C

    For any coloring ρ and any adjacent pair of vertices in C, the pair is either monochromatic (ρ(w) = ρ(v)) or a cut edge (ρ(w) ≠ ρ(v)). Summing the indicator functions over all pairs v, w ∈ C establishes that internal monochromatic pairs plus internal cut pairs equal the total directed edges inside C.

    lines 28–42

    uses Finset.sum_add_distrib, Finset.sum_congr

      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 τ
  4. The number of directed monochromatic pairs inside C under σ is at most 2|C|

    For each v ∈ C, its monochromatic neighbors in C form a subset of all its monochromatic neighbors in G. By the initial defect hypothesis, each v has at most 2 monochromatic neighbors in total. Summing over all |C| vertices bounds the total directed internal monochromatic pairs by 2|C|.

    lines 43–55

    uses Finset.sum_le_sum, Finset.mem_filter, Finset.mem_univ, true_and, le_trans, Finset.card_le_card, Finset.card_filter, Nat.mul_comm

      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]
  5. Under τ there are no internal monochromatic edges in C; under σ there are exactly 2|C| directed internal monochromatic pairs; and the aggregate utility gain on C is exactly |C| automation

    From the welfare and utility decompositions, twice the utility gain equals the change in internal cut edges, which in turn equals the drop in internal monochromatic pairs: 2(∑ u_τ - ∑ u_σ) = M_σ - M_τ. Since the utility gain is at least |C|, this implies M_σ - M_τ ≥ 2|C|. But M_τ ≥ 0 and M_σ ≤ 2|C|, so all inequalities must hold with equality. Automated linear arithmetic closes these three deductions.

    lines 56–58

      have hzero : (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ τ w = τ v then 1 else 0 : ℕ)) = 0 := by omega
      have hfull : (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) = 2 * C.card := by omega
      have hgain_eq : ∑ v ∈ C, maxcut_utility G τ v = (∑ v ∈ C, maxcut_utility G σ v) + C.card := by omega
  6. Every deviator v ∈ C has exactly 2 internal monochromatic neighbors under σ

    Each v ∈ C has at most 2 internal monochromatic neighbors under σ. If any vertex had strictly fewer than 2, the sum over C would be strictly less than 2|C|, contradicting the global equality that there are exactly 2|C| internal monochromatic pairs.

    lines 59–78

    uses le_trans, Finset.card_le_card, Finset.mem_filter, Finset.mem_univ, true_and, Finset.sum_lt_sum, Finset.card_filter, Finset.sum_const, nsmul_eq_mul, Nat.cast_id, Nat.mul_comm, lt_self_iff_false

      have hold_bound (v : V) (hv : v ∈ C) :
          (C.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2 := by
        apply le_trans _ (hdefect v hv)
        apply Finset.card_le_card
        intro w hw
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at *
        exact hw.2
      have hold_full (v : V) (hv : v ∈ C) :
          (C.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 := by
        have hle := hold_bound v hv
        by_contra hne
        have hlt : (C.filter fun w => G.Adj v w ∧ σ w = σ v).card < 2 := by omega
        have hsumlt : (∑ v ∈ C, (C.filter fun w => G.Adj v w ∧ σ w = σ v).card) < ∑ v ∈ C, 2 := by
          apply Finset.sum_lt_sum
          · exact fun u hu => hold_bound u hu
          · exact ⟨v, hv, hlt⟩
        simp only [Finset.card_filter] at hsumlt
        simp only [Finset.sum_const, nsmul_eq_mul] at hsumlt
        rw [hfull] at hsumlt
        simp only [Nat.cast_id, Nat.mul_comm, lt_self_iff_false] at hsumlt
  7. Every deviator v ∈ C gains exactly 1 unit of utility

    Every v ∈ C gains at least 1 in utility. If any vertex gained 2 or more, the total utility gain on C would strictly exceed |C|, contradicting the aggregate utility gain equality. Hence u_τ(v) = u_σ(v) + 1 for each v ∈ C.

    lines 79–90

    uses Nat.succ_le_of_lt, Finset.sum_lt_sum, Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul, mul_one, Nat.cast_id, lt_self_iff_false

      have hgain_one (v : V) (hv : v ∈ C) : maxcut_utility G τ v = maxcut_utility G σ v + 1 := by
        have hle := Nat.succ_le_of_lt (hgain v hv)
        by_contra hne
        have hlt : maxcut_utility G σ v + 1 < maxcut_utility G τ v := by omega
        have hsumlt : (∑ v ∈ C, (maxcut_utility G σ v + 1)) < ∑ v ∈ C, maxcut_utility G τ v := by
          apply Finset.sum_lt_sum
          · intro u hu
            exact Nat.succ_le_of_lt (hgain u hu)
          · exact ⟨v, hv, hlt⟩
        simp only [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul, mul_one] at hsumlt
        rw [hgain_eq] at hsumlt
        simp only [Nat.cast_id, lt_self_iff_false] at hsumlt
  8. Every deviator v ∈ C has total defect 2 under σ and total defect 1 under τ

    Since v has 2 monochromatic neighbors in C and at most 2 in the entire graph, its full defect under σ is exactly 2. Furthermore, Max-Cut utility plus defect equals vertex degree. Since degree is invariant and utility increases by 1, the total defect under τ must decrease by 1, from 2 to 1. This establishes the first conjunct of the theorem.

    lines 91–109

    uses Finset.card_le_card, Finset.mem_filter, Finset.mem_univ, true_and, maxcut_utility_add_monochromatic_card

      have hold_all (v : V) (hv : v ∈ C) :
          (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 := by
        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 hle := Finset.card_le_card hsub
        have hh := hold_full v hv
        have hd := hdefect v hv
        omega
      have hnew_all (v : V) (hv : v ∈ C) :
          (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card = 1 := by
        have huσ := maxcut_utility_add_monochromatic_card G σ v
        have huτ := maxcut_utility_add_monochromatic_card G τ v
        have ha := hold_all v hv
        have hg := hgain_one v hv
        omega
      refine ⟨fun v hv => ⟨hold_all v hv, hnew_all v hv⟩, ?_, ?_⟩
  9. Every monochromatic neighbor of v ∈ C under σ also belongs to C

    Suppose for contradiction that some neighbor w with σ(w) = σ(v) lay outside C. Then the set of internal monochromatic neighbors of v would be a strict subset of its full monochromatic neighborhood, implying its internal defect is strictly less than its total defect. However, both cardinalities were proven to equal 2, a contradiction.

    lines 110–127

    uses Finset.ssubset_iff_subset_ne.mpr, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_filter.mp, Finset.card_lt_card

      · intro v hv w hadj heqvw
        by_contra hwn
        have hs : (C.filter fun w => G.Adj v w ∧ σ w = σ v) ⊂
            Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v := by
          apply Finset.ssubset_iff_subset_ne.mpr
          constructor
          · intro z hz
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at *
            exact hz.2
          · intro heq
            have hin : w ∈ Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v := by
              simp [hadj, heqvw.symm]
            have : w ∈ C.filter fun w => G.Adj v w ∧ σ w = σ v := heq.symm ▸ hin
            exact hwn (Finset.mem_filter.mp this).1
        have hh := Finset.card_lt_card hs
        have hi := hold_full v hv
        have ha := hold_all v hv
        omega
  10. No adjacent vertices in C share the same color under τ

    If there were an adjacent pair v, w ∈ C with τ(v) = τ(w), its indicator term would be positive, forcing the sum of internal monochromatic pairs under τ to be strictly greater than zero. But that sum was shown to be zero, completing the proof.

    lines 128–133

    uses lt_of_lt_of_le, Finset.single_le_sum, Nat.zero_le

      · intro v hv w hw hadj heqvw
        have hpos : 0 < (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ τ w = τ v then 1 else 0 : ℕ)) := by
          apply lt_of_lt_of_le _ (Finset.single_le_sum (fun i _ => Nat.zero_le _) hv)
          apply lt_of_lt_of_le _ (Finset.single_le_sum (fun i _ => Nat.zero_le _) hw)
          simp [hadj, heqvw.symm]
        omega
Nat.succ_le_of_lt
if n < m for natural numbers, then n + 1 ≤ m
Finset.sum_le_sum
if f(i) ≤ g(i) for all i in a finite set, then the sum of f over the set is at most the sum of g
Finset.sum_add_distrib
the sum of f(x) + g(x) over a finite set equals the sum of f(x) plus the sum of g(x)
maxcut_utility_sum_split
the sum of Max-Cut utilities of vertices in S equals the number of cut edges within S plus the cut edges between S and its complement Sᶜ
maxcut_welfare_split
the total Max-Cut welfare decomposes into internal cut edges in S, twice the boundary cut edges between S and Sᶜ, and internal cut edges in Sᶜ
Finset.sum_congr
two sums over equal finite sets are equal if their summands agree on every element
Finset.mem_compl
an element belongs to the complement Sᶜ if and only if it does not belong to S
Finset.mem_filter
an element a belongs to {x ∈ s | p(x)} if and only if a ∈ s and p(a) holds
Finset.mem_univ
every element of a finite type belongs to the universal finset Finset.univ
true_and
the logical equivalence (True ∧ p) = p
le_trans
if a ≤ b and b ≤ c, then a ≤ c
Finset.card_le_card
if s ⊆ t for finite sets, then |s| ≤ |t|
Finset.card_filter
the cardinality of {x ∈ s | p(x)} equals the sum over s of the indicator function if p(x) then 1 else 0
Nat.mul_comm
multiplication of natural numbers is commutative: n * m = m * n
Finset.sum_lt_sum
if f(i) ≤ g(i) everywhere on a finite set and f(i) < g(i) for at least one element, the sum of f is strictly less than the sum of g
Finset.sum_const
summing a constant b over a finite set s yields |s| • b
nsmul_eq_mul
scalar multiplication of a natural number by an element equals their product
Nat.cast_id
the coercion of a natural number to itself is the identity
lt_self_iff_false
the strict inequality x < x is equivalent to False
mul_one
multiplying by 1 on the right is the identity: a * 1 = a
maxcut_utility_add_monochromatic_card
for any vertex v, its Max-Cut utility (cut degree) plus its monochromatic degree equals the graph degree of v
Finset.ssubset_iff_subset_ne.mpr
a subset s ⊆ t with s ≠ t is a strict subset s ⊂ t
Finset.mem_filter.mp
if an element belongs to a filtered set {x ∈ s | p(x)}, it belongs to s and satisfies p
Finset.card_lt_card
a strict subset of a finite set has strictly smaller cardinality
lt_of_lt_of_le
if a < b and b ≤ c, then a < c
Finset.single_le_sum
a single non-negative term is bounded above by the sum over the entire finite set
Nat.zero_le
every natural number is at least zero

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

set_option maxHeartbeats 2000000theorem maxcut_defect_two_equal_welfare_deviation_structure    {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 τ)    (heq : maxcut_welfare G σ = maxcut_welfare G τ) :    (∀ v ∈ C, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 ∧      (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card = 1) ∧    (∀ v ∈ C, ∀ w, G.Adj v w → σ v = σ w → w ∈ C) ∧    (∀ v ∈ C, ∀ w ∈ C, G.Adj v w → τ v ≠ τ w) := 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]  have hzero : (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ τ w = τ v then 1 else 0 : ℕ)) = 0 := by omega  have hfull : (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) = 2 * C.card := by omega  have hgain_eq : ∑ v ∈ C, maxcut_utility G τ v = (∑ v ∈ C, maxcut_utility G σ v) + C.card := by omega  have hold_bound (v : V) (hv : v ∈ C) :      (C.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2 := by    apply le_trans _ (hdefect v hv)    apply Finset.card_le_card    intro w hw    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at *    exact hw.2  have hold_full (v : V) (hv : v ∈ C) :      (C.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 := by    have hle := hold_bound v hv    by_contra hne    have hlt : (C.filter fun w => G.Adj v w ∧ σ w = σ v).card < 2 := by omega    have hsumlt : (∑ v ∈ C, (C.filter fun w => G.Adj v w ∧ σ w = σ v).card) < ∑ v ∈ C, 2 := by      apply Finset.sum_lt_sum      · exact fun u hu => hold_bound u hu      · exact ⟨v, hv, hlt⟩    simp only [Finset.card_filter] at hsumlt    simp only [Finset.sum_const, nsmul_eq_mul] at hsumlt    rw [hfull] at hsumlt    simp only [Nat.cast_id, Nat.mul_comm, lt_self_iff_false] at hsumlt  have hgain_one (v : V) (hv : v ∈ C) : maxcut_utility G τ v = maxcut_utility G σ v + 1 := by    have hle := Nat.succ_le_of_lt (hgain v hv)    by_contra hne    have hlt : maxcut_utility G σ v + 1 < maxcut_utility G τ v := by omega    have hsumlt : (∑ v ∈ C, (maxcut_utility G σ v + 1)) < ∑ v ∈ C, maxcut_utility G τ v := by      apply Finset.sum_lt_sum      · intro u hu        exact Nat.succ_le_of_lt (hgain u hu)      · exact ⟨v, hv, hlt⟩    simp only [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul, mul_one] at hsumlt    rw [hgain_eq] at hsumlt    simp only [Nat.cast_id, lt_self_iff_false] at hsumlt  have hold_all (v : V) (hv : v ∈ C) :      (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 := by    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 hle := Finset.card_le_card hsub    have hh := hold_full v hv    have hd := hdefect v hv    omega  have hnew_all (v : V) (hv : v ∈ C) :      (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card = 1 := by    have huσ := maxcut_utility_add_monochromatic_card G σ v    have huτ := maxcut_utility_add_monochromatic_card G τ v    have ha := hold_all v hv    have hg := hgain_one v hv    omega  refine ⟨fun v hv => ⟨hold_all v hv, hnew_all v hv⟩, ?_, ?_⟩  · intro v hv w hadj heqvw    by_contra hwn    have hs : (C.filter fun w => G.Adj v w ∧ σ w = σ v) ⊂        Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v := by      apply Finset.ssubset_iff_subset_ne.mpr      constructor      · intro z hz        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at *        exact hz.2      · intro heq        have hin : w ∈ Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v := by          simp [hadj, heqvw.symm]        have : w ∈ C.filter fun w => G.Adj v w ∧ σ w = σ v := heq.symm ▸ hin        exact hwn (Finset.mem_filter.mp this).1    have hh := Finset.card_lt_card hs    have hi := hold_full v hv    have ha := hold_all v hv    omega  · intro v hv w hw hadj heqvw    have hpos : 0 < (∑ v ∈ C, ∑ w ∈ C, (if G.Adj v w ∧ τ w = τ v then 1 else 0 : ℕ)) := by      apply lt_of_lt_of_le _ (Finset.single_le_sum (fun i _ => Nat.zero_le _) hv)      apply lt_of_lt_of_le _ (Finset.single_le_sum (fun i _ => Nat.zero_le _) hw)      simp [hadj, heqvw.symm]    omega
See it in the graphDiscuss this resultChallenge it