maxcut_defect_two_equal_welfare_deviation_structure
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
- 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_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 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.
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).
uses
Finset.sum_le_sum,Nat.succ_le_of_lt,Finset.sum_add_distribclassical 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
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 τ.
uses
maxcut_utility_sum_split,maxcut_welfare_split,Finset.sum_congr,Finset.mem_complhave 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]
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.
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 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|.
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]
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.
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
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.
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_falsehave 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
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.
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_falsehave 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
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.
uses
Finset.card_le_card,Finset.mem_filter,Finset.mem_univ,true_and,maxcut_utility_add_monochromatic_cardhave 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⟩, ?_, ?_⟩
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.
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
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.
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
- In lines 56–58, the linear arithmetic solver `omega` simultaneously deduces three tight global equalities (that internal monochromatic edges vanish under τ, attain the maximum possible count 2|C| under σ, and that the total utility gain on C is exactly |C|) by combining the welfare decomposition, utility formulas, and initial defect bounds.
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_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