AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_deviation_two_outsiders

theoremverified

Any strong deviation from a welfare-optimal coloring leaves at least two players outside its coalition.

Statement

theorem maxcut_optimal_deviation_two_outsiders {V : Type} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ}
    (σ τ : V → Fin k) (S : Finset V) (hopt : is_maxcut_optimal G σ)
    (hdev : is_maxcut_strong_deviation G σ S τ) : 2 ≤ Sᶜ.card
Source
Structural helper for OP-89, arXiv:2610.04948 Sec. 4 Question 2. It formalizes the coalition-complement reduction outlined in an earlier session; it does not settle existence of a stable optimum.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_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_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)…

The proof, explained

The theorem is proved by contradiction, assuming fewer than two vertices remain outside the deviating coalition S, so |Sᶜ| ≤ 1. Because every coalition member strictly increases their utility, the coalition's total utility gain exceeds |S| > 0. If Sᶜ = ∅, this coalition gain directly contradicts the welfare-optimality of σ. If Sᶜ is a singleton {w}, the welfare bounds force w to have utility 0 under the new coloring τ and to be connected to every vertex of S under σ; this implies τ is monochromatic, giving 0 utility to all vertices and contradicting the strict utility gain of players in S.

  1. The strong deviation hypothesis yields non-emptiness of the coalition S, constancy outside S, and strict utility gain for every vertex in S.

    We assume classical logic and unpack the definition of `is_maxcut_strong_deviation` into its three components: `hne` (S is non-empty), `hout` (players outside S keep their colors), and `hgain` (every player in S strictly improves their utility).

    lines 5–6

      classical
      obtain ⟨hne, hout, hgain⟩ := hdev
  2. The coalition S gains at least |S| in total utility under τ compared to σ.

    Since each v ∈ S strictly increases its utility (`hgain v`), we have utility(σ, v) + 1 ≤ utility(τ, v) by `Nat.succ_le_of_lt`. Summing over all v ∈ S via `Finset.sum_le_sum` and distributing the sum with `Finset.sum_add_distrib` shows that the coalition's total utility under τ is at least its total utility under σ plus |S|.

    lines 7–10

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

      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
  3. Total welfare decomposes into the sums over S and Sᶜ, with τ having at most the welfare of σ, and |S| > 0.

    Using `Finset.sum_add_sum_compl`, total welfare under each coloring decomposes as the sum of utilities over S plus the sum over Sᶜ. By welfare optimality of σ (`hopt`), the total welfare of τ cannot exceed that of σ. Furthermore, non-emptiness of S implies |S| > 0 (`Finset.card_pos.mpr`).

    lines 11–15

    uses Finset.sum_add_sum_compl, Finset.card_pos.mpr

      have hσ := Finset.sum_add_sum_compl S (maxcut_utility G σ)
      have hτ := Finset.sum_add_sum_compl S (maxcut_utility G τ)
      have hop := hopt τ
      change (∑ v, maxcut_utility G τ v) ≤ (∑ v, maxcut_utility G σ v) at hop
      have hpos : 0 < S.card := Finset.card_pos.mpr hne
  4. Assume for contradiction that at most one player is outside S, i.e., |Sᶜ| ≤ 1.

    We assume for contradiction that ¬(2 ≤ |Sᶜ|). Linear integer arithmetic immediately gives |Sᶜ| ≤ 1.

    lines 16–17

      by_contra hc
      have hle : Sᶜ.card ≤ 1 := by omega
  5. The complement Sᶜ cannot be empty.

    If Sᶜ = ∅, the sum of utilities over Sᶜ is 0 by `Finset.sum_empty`, so total welfare is just the sum over S. But the coalition S strictly increases total welfare by at least |S| > 0, which contradicts the welfare optimality of σ.

    lines 18–20

    uses Finset.sum_empty

      by_cases he : Sᶜ = ∅
      · simp only [he, Finset.sum_empty] at hσ hτ
        omega
  6. The complement Sᶜ is a singleton {w}, and the sum of utilities over Sᶜ is simply the utility of w.

    Since Sᶜ ≠ ∅ (`Finset.nonempty_iff_ne_empty.mpr`), there exists an outsider w ∈ Sᶜ. Because |Sᶜ| ≤ 1, every element in Sᶜ equals w (`Finset.card_le_one.mp`, `Finset.mem_singleton`), establishing Sᶜ = {w}. Rewriting with `Finset.sum_singleton`, the sum over Sᶜ in the welfare equations reduces to the utility of w.

    lines 21–31

    uses Finset.nonempty_iff_ne_empty.mpr, Finset.mem_singleton, Finset.card_le_one.mp, Finset.mem_singleton.mp, Finset.sum_singleton

      · obtain ⟨w, hw⟩ := Finset.nonempty_iff_ne_empty.mpr he
        have hsingle : Sᶜ = {w} := by
          ext v
          constructor
          · intro hv
            simp only [Finset.mem_singleton]
            exact Finset.card_le_one.mp hle v hv w hw
          · intro hv
            have hvw : v = w := Finset.mem_singleton.mp hv
            simpa [hvw] using hw
        simp only [hsingle, Finset.sum_singleton] at hσ hτ
  7. The cut-neighborhood A of w under σ is contained in S, hence utility(σ, w) ≤ |S|.

    Let A be the set of neighbors of w that have a different color from w under σ. Because the graph has no self-loops, w cannot belong to A. Since the only vertex outside S is w, any vertex not in S would have to equal w (`Finset.mem_compl.mpr`), a contradiction. Thus A ⊆ S, and by `Finset.card_le_card`, utility(σ, w) = |A| ≤ |S|.

    lines 32–42

    uses Finset.mem_compl.mpr, Finset.mem_filter.mp, Finset.card_le_card

        let A := Finset.univ.filter fun v => G.Adj w v ∧ σ v ≠ σ w
        have hsub : A ⊆ S := by
          intro v hv
          by_contra hvs
          have hvw : v = w := by
            have : v ∈ Sᶜ := Finset.mem_compl.mpr hvs
            simpa [hsingle] using this
          have ha := (Finset.mem_filter.mp hv).2.1
          subst v
          exact G.loopless.irrefl w ha
        have hbound : maxcut_utility G σ w ≤ S.card := Finset.card_le_card hsub
  8. The outsider w has zero utility under τ, and A = S.

    Comparing the decomposed welfares with the coalition gain inequality gives |S| + utility(τ, w) ≤ utility(σ, w). Combined with utility(σ, w) ≤ |S|, linear integer arithmetic forces utility(τ, w) = 0 and |S| ≤ utility(σ, w) = |A|. Since A ⊆ S and |S| ≤ |A|, `Finset.eq_of_subset_of_card_le` proves A = S.

    lines 43–46

    uses Finset.eq_of_subset_of_card_le

        have hzero : maxcut_utility G τ w = 0 := by omega
        have hfull : A = S := Finset.eq_of_subset_of_card_le hsub (by
          change S.card ≤ maxcut_utility G σ w
          omega)
  9. Every vertex in the graph receives the same color under τ as w.

    For any v ∈ S, since A = S, v is adjacent to w (`Finset.mem_filter.mp`). If τ(v) ≠ τ(w), then v would be in the set of cut-neighbors of w under τ (`Finset.mem_filter.mpr`, `Finset.mem_univ`). But utility(τ, w) = 0, so this set is empty (`Finset.card_eq_zero.mp`), a contradiction. For v ∉ S, v must equal w (`Finset.mem_compl.mpr`), so τ(v) = τ(w) holds trivially. Hence τ is monochromatic.

    lines 47–60

    uses Finset.mem_filter.mp, Finset.mem_univ, Finset.mem_filter.mpr, Finset.card_eq_zero.mp, Finset.mem_compl.mpr

        have hconst : ∀ v, τ v = τ w := by
          intro v
          by_cases hv : v ∈ S
          · have ha : G.Adj w v := (Finset.mem_filter.mp (hfull.symm ▸ hv)).2.1
            by_contra hne
            have hmem : v ∈ Finset.univ.filter (fun z => G.Adj w z ∧ τ z ≠ τ w) :=
              Finset.mem_filter.mpr ⟨Finset.mem_univ _, ha, hne⟩
            have hempty : (Finset.univ.filter fun z => G.Adj w z ∧ τ z ≠ τ w) = ∅ :=
              Finset.card_eq_zero.mp hzero
            simpa [hempty] using hmem
          · have : v = w := by
              have := Finset.mem_compl.mpr hv
              simpa [hsingle] using this
            simp [this]
  10. Monochromatic coloring yields utility 0 everywhere, contradicting that coalition members strictly gained utility.

    Because τ assigns the same color to all vertices, no edge has endpoints of different colors, meaning utility(τ, v) = 0 for every vertex v. Choosing any vertex v ∈ S (which exists since S is non-empty), its strict improvement requires 0 ≤ utility(σ, v) < utility(τ, v) = 0, an impossibility.

    lines 61–64

        obtain ⟨v, hv⟩ := hne
        have hgainv := hgain v hv
        have hu : maxcut_utility G τ v = 0 := by simp [maxcut_utility, hconst]
        omega
Finset.card_eq_zero.mp
A finite set with cardinality zero is empty.
Finset.card_le_one.mp
If a finite set has at most one element, then any two elements in it are equal.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most that of the other.
Finset.card_pos.mpr
A non-empty finite set has strictly positive cardinality.
Finset.eq_of_subset_of_card_le
A subset of a finite set with at least the cardinality of the larger set is equal to the larger set.
Finset.mem_compl.mpr
An element not in a set belongs to its complement.
Finset.mem_filter.mp
An element in a filtered subset satisfies the filtering predicate.
Finset.mem_filter.mpr
An element in a set satisfying a predicate belongs to the filtered subset.
Finset.mem_singleton
An element belongs to a singleton set if and only if it equals the set's single element.
Finset.mem_singleton.mp
If an element belongs to a singleton set, it is equal to the element of that singleton.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.nonempty_iff_ne_empty.mpr
If a finite set is not equal to the empty set, it is non-empty.
Finset.sum_add_distrib
The sum of a sum of functions over a finite set equals the sum of their individual sums.
Finset.sum_add_sum_compl
The sum of a function over a finite set plus its sum over the complement equals the sum over the entire domain.
Finset.sum_empty
The sum of any function over the empty set is zero.
Finset.sum_le_sum
If one function is pointwise less than or equal to another on a finite set, its sum is also less than or equal.
Finset.sum_singleton
The sum of a function over a singleton set equals the value of the function at that element.
Nat.succ_le_of_lt
If one natural number is strictly less than another, then its successor is less than or equal to that number.

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

theorem maxcut_optimal_deviation_two_outsiders {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ}    (σ τ : V → Fin k) (S : Finset V) (hopt : is_maxcut_optimal G σ)    (hdev : is_maxcut_strong_deviation G σ S τ) : 2 ≤ Sᶜ.card := by  classical  obtain ⟨hne, hout, hgain⟩ := hdev  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 hσ := Finset.sum_add_sum_compl S (maxcut_utility G σ)  have hτ := Finset.sum_add_sum_compl S (maxcut_utility G τ)  have hop := hopt τ  change (∑ v, maxcut_utility G τ v) ≤ (∑ v, maxcut_utility G σ v) at hop  have hpos : 0 < S.card := Finset.card_pos.mpr hne  by_contra hc  have hle : Sᶜ.card ≤ 1 := by omega  by_cases he : Sᶜ = ∅  · simp only [he, Finset.sum_empty] at hσ hτ    omega  · obtain ⟨w, hw⟩ := Finset.nonempty_iff_ne_empty.mpr he    have hsingle : Sᶜ = {w} := by      ext v      constructor      · intro hv        simp only [Finset.mem_singleton]        exact Finset.card_le_one.mp hle v hv w hw      · intro hv        have hvw : v = w := Finset.mem_singleton.mp hv        simpa [hvw] using hw    simp only [hsingle, Finset.sum_singleton] at hσ hτ    let A := Finset.univ.filter fun v => G.Adj w v ∧ σ v ≠ σ w    have hsub : A ⊆ S := by      intro v hv      by_contra hvs      have hvw : v = w := by        have : v ∈ Sᶜ := Finset.mem_compl.mpr hvs        simpa [hsingle] using this      have ha := (Finset.mem_filter.mp hv).2.1      subst v      exact G.loopless.irrefl w ha    have hbound : maxcut_utility G σ w ≤ S.card := Finset.card_le_card hsub    have hzero : maxcut_utility G τ w = 0 := by omega    have hfull : A = S := Finset.eq_of_subset_of_card_le hsub (by      change S.card ≤ maxcut_utility G σ w      omega)    have hconst : ∀ v, τ v = τ w := by      intro v      by_cases hv : v ∈ S      · have ha : G.Adj w v := (Finset.mem_filter.mp (hfull.symm ▸ hv)).2.1        by_contra hne        have hmem : v ∈ Finset.univ.filter (fun z => G.Adj w z ∧ τ z ≠ τ w) :=          Finset.mem_filter.mpr ⟨Finset.mem_univ _, ha, hne⟩        have hempty : (Finset.univ.filter fun z => G.Adj w z ∧ τ z ≠ τ w) = ∅ :=          Finset.card_eq_zero.mp hzero        simpa [hempty] using hmem      · have : v = w := by          have := Finset.mem_compl.mpr hv          simpa [hsingle] using this        simp [this]    obtain ⟨v, hv⟩ := hne    have hgainv := hgain v hv    have hu : maxcut_utility G τ v = 0 := by simp [maxcut_utility, hconst]    omega
See it in the graphDiscuss this resultChallenge it