AFTD Auto-Formalizing Theoretical Domains

maxcut_defect_two_deviation_welfare_nondecreasing

theoremverified

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

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.

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

    lines 9–10

      classical
      obtain ⟨hne, hout, hgain⟩ := hdev
  2. The 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|.

    lines 11–14

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

      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
  3. 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ᶜ.

    lines 15–18

    uses maxcut_utility_sum_split, maxcut_welfare_split

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

    lines 19–23

    uses Finset.sum_congr, Finset.mem_compl

      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]
  5. 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 τ.

    lines 24–38

    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 τ
  6. 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.

    lines 39–51

    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]
  7. 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 τ.

    line 52

      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.

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