maxcut_optimal_deviation_two_outsiders
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.
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).
classical obtain ⟨hne, hout, hgain⟩ := hdevThe 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|.
uses
Finset.sum_le_sum,Nat.succ_le_of_lt,Finset.sum_add_distribhave 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
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`).
uses
Finset.sum_add_sum_compl,Finset.card_pos.mprhave 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
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.
by_contra hc have hle : Sᶜ.card ≤ 1 := by omega
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 σ.
uses
Finset.sum_emptyby_cases he : Sᶜ = ∅ · simp only [he, Finset.sum_empty] at hσ hτ omega
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.
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τ
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|.
uses
Finset.mem_compl.mpr,Finset.mem_filter.mp,Finset.card_le_cardlet 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
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.
uses
Finset.eq_of_subset_of_card_lehave 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)
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.
uses
Finset.mem_filter.mp,Finset.mem_univ,Finset.mem_filter.mpr,Finset.card_eq_zero.mp,Finset.mem_compl.mprhave 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]
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.
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.
- In this formalization, `maxcut_welfare` is defined as the sum of individual vertex utilities, which corresponds to twice the number of cut edges in graph-theoretic terms.
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.
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