AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_strong_of_degree_le

theoremverifiedformalization

For every k ≥ 1: on every finite simple graph whose maximum degree is at most 2k − 1, every optimal coloring of the unweighted Max-k-Cut game is a strong equilibrium. In terms of the open problem, Δ*(k) ≥ 2k − 1.

Statement

theorem maxcut_optimal_strong_of_degree_le (k : ℕ) (hk : 1 ≤ k) :
    maxcut_optimal_strong_up_to_degree k (2 * k - 1)
Formalizes
arXiv:2610.04948, Corollary 9 (originally arXiv:1810.09278, Proposition 9), stated there for k ≥ 2; the Lean version allows k ≥ 1 (k = 1 is trivial). Proof follows the paper's internal-conflict counting: optimal colorings are Nash, so each vertex has at most one same-colored neighbour, and the deviation identity (Lemma 7) then rules out every strong deviation
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • maxcut_optimal_strong_up_to_degreeFor k and D: on every finite simple graph of maximum degree at most D, every optimal coloring of the Max-k-Cut game with k colors is a…
  • maxcut_optimal_same_color_leAt an optimal coloring σ of the Max-k-Cut game, for every vertex v and every color c, the number of neighbours of v with color σ(v) is at…
  • 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 2

The proof, explained

The proof proceeds by contradiction: suppose an optimal coloring σ admits a strong deviation (S, τ) by a nonempty coalition S, where every vertex in S strictly increases its utility. First, the degree bound ≤ 2k - 1 combined with optimality implies that each vertex shares its color with at most one neighbor, which bounds the increase in internal cut edges within S by at most |S|. Expressing total welfare and utility sums in terms of the cut decomposition across S and Sᶜ, the deviation must increase total welfare by at least 2|S| - |S| = |S| ≥ 1. This contradicts the optimality of σ, which requires W(τ) ≤ W(σ).

  1. Suppose for contradiction that there exists a strong deviation from the optimal coloring.

    Assume classical logic and consider a graph G with maximum degree at most 2k - 1, an optimal coloring σ, and a candidate strong deviation (S, τ). Unpacking the definition of strong deviation gives that S is nonempty (hne), τ agrees with σ outside S (hagree), and every vertex v ∈ S achieves strictly greater utility under τ than under σ (hgain). The goal is to reach False.

    lines 3–5

      classical
      intro V _ G _ hdeg σ hopt S τ hdev
      obtain ⟨hne, hagree, hgain⟩ := hdev
  2. Under the optimal coloring σ, every vertex shares its color with at most one neighbor.

    Fix a vertex v. Partitioning its neighbors by their assigned color classes using `Finset.card_eq_sum_card_fiberwise`, `Finset.mem_coe.2`, `Finset.mem_univ`, and `Finset.filter_filter`, the degree of v is the sum of the sizes of these color classes. By the maximum degree assumption, this degree is at most 2k - 1 (`SimpleGraph.card_neighborFinset_eq_degree`, `SimpleGraph.neighborFinset_eq_filter`). Because σ is optimal, v has at least as many neighbors in every color class c as in its own color class σ(v) (`maxcut_optimal_same_color_le`). Summing this lower bound over all k colors gives k * |{w ∈ N(v) : σ(w) = σ(v)}| ≤ deg(v) ≤ 2k - 1 (`Finset.sum_le_sum`, `Finset.sum_const`, `Finset.card_univ`, `Fintype.card_fin`, `smul_eq_mul`). If v shared its color with 2 or more neighbors, this product would be at least 2k (`Nat.mul_le_mul_left`), contradicting 2k ≤ 2k - 1.

    lines 6–25

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_coe.2, Finset.mem_univ, Finset.filter_filter, SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter, Finset.sum_le_sum, maxcut_optimal_same_color_le, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul, Nat.mul_le_mul_left

      -- at most one neighbour shares each vertex's color
      have hmono : ∀ v, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1 := by
        intro v
        have hsum : (Finset.univ.filter fun w => G.Adj v w).card =
            ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := by
          rw [Finset.card_eq_sum_card_fiberwise (f := σ) (t := Finset.univ)
            (fun _ _ => Finset.mem_coe.2 (Finset.mem_univ _))]
          simp only [Finset.filter_filter]
        have hdv : (Finset.univ.filter fun w => G.Adj v w).card ≤ 2 * k - 1 := by
          have := hdeg v
          rwa [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter]
            at this
        have hlow : ∑ _c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤
            ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card :=
          Finset.sum_le_sum fun c _ => maxcut_optimal_same_color_le G σ hopt v c
        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hlow
        by_contra hc
        have : k * 2 ≤ k * (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card :=
          Nat.mul_le_mul_left k (by omega)
        omega
  3. Total welfare and the sum of utilities on S decompose across S and Sᶜ, with cut edges inside Sᶜ remaining unchanged.

    By `maxcut_welfare_split`, total welfare decomposes for both σ and τ into cut edges within S, twice the cut edges between S and Sᶜ, and cut edges within Sᶜ. By `maxcut_utility_sum_split`, the sum of utilities on S decomposes into cut edges within S plus cut edges between S and Sᶜ. Because τ agrees with σ on Sᶜ (`hagree`, `Finset.mem_compl.1`), the cut edges entirely within Sᶜ are identical under both colorings (`Finset.sum_congr`).

    lines 26–33

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

      have hS := maxcut_welfare_split G σ S
      have hT := maxcut_welfare_split G τ S
      have hC : ∑ x ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj x w ∧ τ w ≠ τ x then 1 else 0 : ℕ) =
          ∑ x ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj x w ∧ σ w ≠ σ x then 1 else 0 : ℕ) := by
        refine Finset.sum_congr rfl fun x hx => Finset.sum_congr rfl fun w hw => ?_
        rw [hagree x (Finset.mem_compl.1 hx), hagree w (Finset.mem_compl.1 hw)]
      have hUS := maxcut_utility_sum_split G σ S
      have hUT := maxcut_utility_sum_split G τ S
  4. The sum of utilities on S increases by at least |S| under τ.

    Each vertex v ∈ S strictly increases its utility under τ, so utility(τ, v) ≥ utility(σ, v) + 1 (`Nat.succ_le_of_lt`). Summing over all vertices in S yields ∑_{v ∈ S} utility(σ, v) + |S| ≤ ∑_{v ∈ S} utility(τ, v) (`Finset.sum_le_sum`, `Finset.sum_add_distrib`).

    lines 34–36

    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
  5. Pointwise, whether an edge is cut by τ is bounded by its cut status under σ plus its monochromatic status under σ.

    For any pair of vertices v, w, we split on whether {v, w} is an edge cut by τ (`em`). If it is, then under σ either σ(w) ≠ σ(v) or σ(w) = σ(v) (`if_pos`), so at least one term on the right-hand side is 1. If {v, w} is not cut by τ, the indicator on the left-hand side is 0, which is trivially at most the right-hand side (`if_neg`).

    lines 37–46

    uses em, if_pos, if_neg

      have hpt : ∀ v w, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤
          (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) +
            (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := by
        intro v w
        rcases em (G.Adj v w ∧ τ w ≠ τ v) with h1 | h1
        · rw [if_pos h1]
          rcases em (σ w = σ v) with h2 | h2
          · rw [if_pos (⟨h1.1, h2⟩ : G.Adj v w ∧ σ w = σ v)]; omega
          · rw [if_pos (⟨h1.1, h2⟩ : G.Adj v w ∧ σ w ≠ σ v)]; omega
        · rw [if_neg h1]; omega
  6. The internal cut edges within S under τ exceed those under σ by at most |S|.

    Summing the pointwise edge bound over all pairs v, w ∈ S (`Finset.sum_le_sum`, `Finset.sum_add_distrib`), the internal cut edges under τ are bounded by those under σ plus the sum over v ∈ S of neighbors in S sharing the color σ(v). For each v ∈ S, its monochromatic neighbors in S are a subset of its monochromatic neighbors in the entire graph (`Finset.sum_le_sum_of_subset`, `Finset.subset_univ`, `Finset.card_filter`), which is at most 1 by the earlier step `hmono`. Summing 1 over all vertices in S adds at most |S| (`Finset.sum_add_distrib`).

    lines 47–68

    uses Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_le_sum_of_subset, Finset.subset_univ, Finset.card_filter

      have hA : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤
          ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + S.card := by
        calc ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ)
            ≤ ∑ v ∈ S, (∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + 1) := by
              refine Finset.sum_le_sum fun v _ => ?_
              calc ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ)
                  ≤ ∑ w ∈ S, ((if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) +
                      (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) :=
                    Finset.sum_le_sum fun w _ => hpt v w
                _ = ∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) +
                      ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) :=
                    Finset.sum_add_distrib
                _ ≤ _ := by
                    have : ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) ≤ 1 := by
                      calc ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)
                          ≤ ∑ w, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) :=
                            Finset.sum_le_sum_of_subset (Finset.subset_univ S)
                        _ = (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card :=
                            (Finset.card_filter _ _).symm
                        _ ≤ 1 := hmono v
                    omega
          _ = _ := by simp [Finset.sum_add_distrib]
  7. The deviation strictly increases total welfare, contradicting the optimality of σ.

    Because S is nonempty, |S| ≥ 1 (`Finset.card_pos.2`). By optimality of σ, total welfare cannot strictly increase: W(τ) ≤ W(σ). However, from the welfare and utility sum decompositions, W(τ) - W(σ) = 2(∑_{v ∈ S} utility(τ, v) - ∑_{v ∈ S} utility(σ, v)) - (E_τ(S, S) - E_σ(S, S)) ≥ 2|S| - |S| = |S| ≥ 1 > 0, so W(τ) > W(σ). The linear arithmetic tactic `omega` detects this contradiction from the established system of bounds.

    lines 69–71

    uses Finset.card_pos.2

      have hcard : 1 ≤ S.card := Finset.card_pos.2 hne
      have hopt' := hopt τ
      omega
Finset.card_eq_sum_card_fiberwise
The size of a finite set equals the sum of the sizes of its fibers under a map into a target set.
Finset.mem_coe.2
An element belongs to the coercion of a finset if and only if it belongs to the finset.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.filter_filter
Filtering a finset successively by two predicates is equivalent to filtering by their conjunction.
SimpleGraph.card_neighborFinset_eq_degree
The degree of a vertex in a simple graph equals the number of vertices in its neighbor finset.
SimpleGraph.neighborFinset_eq_filter
The neighbor finset of a vertex equals the finset of all vertices in the graph adjacent to it.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finset, then the sum of f over the finset is at most the sum of g.
maxcut_optimal_same_color_le
Under an optimal Max-Cut coloring, a vertex has at least as many neighbors in any given color class as in its own color class.
Finset.sum_const
The sum of a constant value over a finset equals the cardinality of the finset multiplied by the constant.
Finset.card_univ
The cardinality of the universal finset equals the cardinality of the underlying finite type.
Fintype.card_fin
The cardinality of the finite type `Fin n` is n.
smul_eq_mul
Scalar multiplication on natural numbers is standard multiplication.
Nat.mul_le_mul_left
Multiplication on the left by a natural number preserves the order: if n ≤ m then k * n ≤ k * m.
maxcut_welfare_split
The total welfare of a coloring decomposes into the cut edges within S, twice the cut edges between S and the complement of S, and the cut edges within the complement of S.
Finset.sum_congr
If two finsets are equal and the summands agree pointwise on the set, their sums are equal.
Finset.mem_compl.1
An element in the complement of a finset does not belong to the finset.
maxcut_utility_sum_split
The sum of utilities of vertices in S equals the cut edges within S plus the cut edges between S and the complement of S.
Nat.succ_le_of_lt
For natural numbers, n < m implies 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.
em
The law of excluded middle: for any proposition, either it or its negation is true.
if_pos
An if-then-else expression evaluates to the 'then' branch when the condition is true.
if_neg
An if-then-else expression evaluates to the 'else' branch when the condition is false.
Finset.sum_le_sum_of_subset
Summing a non-negative function over a subset yields at most the sum over the superset.
Finset.subset_univ
Every finset of a finite type is a subset of the universal finset `Finset.univ`.
Finset.card_filter
The cardinality of a filtered finset equals the sum of the indicator values of the filtering predicate.
Finset.card_pos.2
A finset has strictly positive cardinality if and only if it is nonempty.

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_strong_of_degree_le (k : ℕ) (hk : 1 ≤ k) :    maxcut_optimal_strong_up_to_degree k (2 * k - 1) := by  classical  intro V _ G _ hdeg σ hopt S τ hdev  obtain ⟨hne, hagree, hgain⟩ := hdev  -- at most one neighbour shares each vertex's color  have hmono : ∀ v, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1 := by    intro v    have hsum : (Finset.univ.filter fun w => G.Adj v w).card =        ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := by      rw [Finset.card_eq_sum_card_fiberwise (f := σ) (t := Finset.univ)        (fun _ _ => Finset.mem_coe.2 (Finset.mem_univ _))]      simp only [Finset.filter_filter]    have hdv : (Finset.univ.filter fun w => G.Adj v w).card ≤ 2 * k - 1 := by      have := hdeg v      rwa [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter]        at this    have hlow : ∑ _c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤        ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card :=      Finset.sum_le_sum fun c _ => maxcut_optimal_same_color_le G σ hopt v c    simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hlow    by_contra hc    have : k * 2 ≤ k * (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card :=      Nat.mul_le_mul_left k (by omega)    omega  have hS := maxcut_welfare_split G σ S  have hT := maxcut_welfare_split G τ S  have hC : ∑ x ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj x w ∧ τ w ≠ τ x then 1 else 0 : ℕ) =      ∑ x ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj x w ∧ σ w ≠ σ x then 1 else 0 : ℕ) := by    refine Finset.sum_congr rfl fun x hx => Finset.sum_congr rfl fun w hw => ?_    rw [hagree x (Finset.mem_compl.1 hx), hagree w (Finset.mem_compl.1 hw)]  have hUS := maxcut_utility_sum_split G σ S  have hUT := maxcut_utility_sum_split G τ S  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 hpt : ∀ v w, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤      (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) +        (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := by    intro v w    rcases em (G.Adj v w ∧ τ w ≠ τ v) with h1 | h1    · rw [if_pos h1]      rcases em (σ w = σ v) with h2 | h2      · rw [if_pos (⟨h1.1, h2⟩ : G.Adj v w ∧ σ w = σ v)]; omega      · rw [if_pos (⟨h1.1, h2⟩ : G.Adj v w ∧ σ w ≠ σ v)]; omega    · rw [if_neg h1]; omega  have hA : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ) ≤      ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + S.card := by    calc ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ)        ≤ ∑ v ∈ S, (∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) + 1) := by          refine Finset.sum_le_sum fun v _ => ?_          calc ∑ w ∈ S, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ)              ≤ ∑ w ∈ S, ((if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) +                  (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) :=                Finset.sum_le_sum fun w _ => hpt v w            _ = ∑ w ∈ S, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) +                  ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) :=                Finset.sum_add_distrib            _ ≤ _ := by                have : ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) ≤ 1 := by                  calc ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)                      ≤ ∑ w, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) :=                        Finset.sum_le_sum_of_subset (Finset.subset_univ S)                    _ = (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card :=                        (Finset.card_filter _ _).symm                    _ ≤ 1 := hmono v                omega      _ = _ := by simp [Finset.sum_add_distrib]  have hcard : 1 ≤ S.card := Finset.card_pos.2 hne  have hopt' := hopt τ  omega
See it in the graphDiscuss this resultChallenge it