AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_same_color_le

theoremverified

At 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 most the number of neighbours with color c (optimal colorings are Nash equilibria).

Statement

theorem maxcut_optimal_same_color_le {V : Type} [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (hopt : is_maxcut_optimal G σ) (v : V)
    (c : Fin k) :
    (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤
      (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card
Source
step towards maxcut_optimal_strong_of_degree_le (arXiv:2610.04948, Corollary 9)
Verified
06 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).
  • 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 8

The proof, explained

The proof evaluates the local optimality of σ by comparing it to the coloring τ obtained by recoloring vertex v to c while leaving all other vertices unchanged. Because all edges disjoint from v are unaffected by this change, the change in social welfare is determined entirely by the change in the utility of v, meaning that optimality of σ forces the utility of v under τ to be at most its utility under σ. Expressing utility as the total degree of v minus the number of neighbors sharing the vertex's color translates this utility inequality into the required bound: v has at most as many neighbors of color σ(v) as it has of color c.

  1. Let τ be the coloring obtained from σ by recoloring vertex v with color c, leaving all other vertices unchanged.

    We introduce the coloring τ = Function.update(σ, v, c), which agrees with σ on every vertex except possibly v, where its value is set to c.

    lines 6–7

      classical
      set τ := Function.update σ v c with hτ
  2. The cut edges strictly within V \ {v} contribute identically to welfare under σ and under τ.

    Decomposing social welfare around the singleton {v} using `maxcut_welfare_split`, the edges with both endpoints in {v}ᶜ do not involve v. By `Function.update_of_ne`, τ and σ agree on all vertices in {v}ᶜ, so the summands for edges within {v}ᶜ are identical. Applying `Finset.sum_congr` shows that this term is identical under σ and τ.

    lines 8–17

    uses maxcut_welfare_split, Finset.sum_congr, Function.update_of_ne

      have hS := maxcut_welfare_split G σ {v}
      have hT := maxcut_welfare_split G τ {v}
      have hC : ∑ x ∈ ({v} : Finset V)ᶜ, ∑ w ∈ ({v} : Finset V)ᶜ,
          (if G.Adj x w ∧ τ w ≠ τ x then 1 else 0 : ℕ) =
          ∑ x ∈ ({v} : Finset V)ᶜ, ∑ w ∈ ({v} : Finset V)ᶜ,
          (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 => ?_
        have hx' : x ≠ v := by simpa using hx
        have hw' : w ≠ v := by simpa using hw
        simp [hτ, Function.update_of_ne hx', Function.update_of_ne hw']
  3. For both σ and τ, the social welfare simplifies to twice the utility of v plus the unaffected cut edges within V \ {v}.

    By `maxcut_utility_sum_split`, the utility of v is the sum of cut edges within {v} and cut edges between {v} and {v}ᶜ. Since simple graphs have no self-loops (`SimpleGraph.irrefl`), edges within {v} evaluate to 0 (`false_and`, `if_false`). Simplifying the singleton sums with `Finset.sum_singleton` reveals that the welfare under both σ and τ equals 2 * maxcut_utility(v) plus the cut edges within {v}ᶜ.

    lines 18–20

    uses maxcut_utility_sum_split, Finset.sum_singleton, SimpleGraph.irrefl, false_and, if_false

      have hUS := maxcut_utility_sum_split G σ {v}
      have hUT := maxcut_utility_sum_split G τ {v}
      simp only [Finset.sum_singleton, SimpleGraph.irrefl, false_and, if_false] at hS hT hUS hUT
  4. The utility of v under τ is at most its utility under σ.

    Since σ maximizes welfare (`hopt`), the welfare under τ is at most that under σ. Because the edges strictly within {v}ᶜ contribute the same amount to both welfares, the inequality reduces to 2 * maxcut_utility(τ, v) ≤ 2 * maxcut_utility(σ, v), which linear arithmetic (`omega`) simplifies to maxcut_utility(τ, v) ≤ maxcut_utility(σ, v).

    lines 21–22

      have hle : maxcut_utility G τ v ≤ maxcut_utility G σ v := by
        have := hopt τ; omega
  5. The utility of v under τ equals the number of neighbors of v whose color under σ is not c.

    By definition, the utility of v under τ counts neighbors w of v with τ(w) ≠ τ(v). Since τ(v) = c, and for any neighbor w ≠ v we have τ(w) = σ(w) by `Function.update_of_ne`, the condition τ(w) ≠ τ(v) is equivalent to σ(w) ≠ c (and w = v is excluded because G has no self-loops). Applying `Finset.filter_congr` equates the sets and their cardinalities.

    lines 23–30

    uses Finset.filter_congr, Function.update_of_ne

      have hτu : maxcut_utility G τ v =
          (Finset.univ.filter fun w => G.Adj v w ∧ σ w ≠ c).card := by
        unfold maxcut_utility
        congr 1
        refine Finset.filter_congr fun w _ => ?_
        by_cases hw : w = v
        · subst hw; simp
        · simp [hτ, Function.update_of_ne hw]
  6. The neighbors of v partition into those with color σ(v) (respectively c) and those without, summing to the degree of v.

    By `Finset.card_filter_add_card_filter_not`, the neighbors of v with color σ(v) plus those with color different from σ(v) equal the total degree of v. The same partitioning holds for color c. Simplifying the nested filters with `Finset.filter_filter` puts both equations in terms of conjunctions on the neighborhood of v.

    lines 31–35

    uses Finset.card_filter_add_card_filter_not, Finset.filter_filter

      have h1 := Finset.card_filter_add_card_filter_not
        (s := Finset.univ.filter fun w => G.Adj v w) (fun w => σ w = σ v)
      have h2 := Finset.card_filter_add_card_filter_not
        (s := Finset.univ.filter fun w => G.Adj v w) (fun w => σ w = c)
      simp only [Finset.filter_filter] at h1 h2
  7. The number of neighbors of v with color σ(v) is at most the number of neighbors with color c.

    Substituting the formula for the utility under τ into the utility inequality shows that the number of neighbors with color different from c is at most the number of neighbors with color different from σ(v). Since the total number of neighbors is identical in both partitions, subtracting from the degree shows that the number of neighbors sharing color σ(v) is at most the number of neighbors sharing color c; linear arithmetic (`omega`) after rewriting inequalities with `ne_eq` completes the deduction.

    lines 36–39

    uses ne_eq

      rw [hτu] at hle
      unfold maxcut_utility at hle
      simp only [ne_eq] at hle h1 h2
      omega
maxcut_welfare_split
The total cut welfare of a coloring decomposes into cut edges within a subset S, twice the cut edges between S and its complement, and cut edges within the complement.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Function.update_of_ne
Updating a function at a point a' does not alter its value at any distinct point a ≠ a'.
maxcut_utility_sum_split
The sum of utilities over a subset S equals the cut edges within S plus the cut edges between S and its complement.
Finset.sum_singleton
The sum of a function over a singleton set {a} is the value of the function at a.
SimpleGraph.irrefl
In a simple graph, no vertex is adjacent to itself (no self-loops).
false_and
The conjunction of False with any proposition is False.
if_false
An if-then-else expression whose condition is False simplifies to the else branch.
Finset.filter_congr
Filtering a finite set by two predicates produces the same set if the predicates are logically equivalent on all elements of the set.
Finset.card_filter_add_card_filter_not
The number of elements in a finite set satisfying a predicate plus the number not satisfying it equals the cardinality of the set.
Finset.filter_filter
Filtering a finite set successively by two predicates is equivalent to filtering once by their conjunction.
ne_eq
The inequality a ≠ b is definitionally identical to the negation ¬(a = b).

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_same_color_le {V : Type} [Fintype V] (G : SimpleGraph V)    [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (hopt : is_maxcut_optimal G σ) (v : V)    (c : Fin k) :    (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤      (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := by  classical  set τ := Function.update σ v c with hτ  have hS := maxcut_welfare_split G σ {v}  have hT := maxcut_welfare_split G τ {v}  have hC : ∑ x ∈ ({v} : Finset V)ᶜ, ∑ w ∈ ({v} : Finset V)ᶜ,      (if G.Adj x w ∧ τ w ≠ τ x then 1 else 0 : ℕ) =      ∑ x ∈ ({v} : Finset V)ᶜ, ∑ w ∈ ({v} : Finset V)ᶜ,      (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 => ?_    have hx' : x ≠ v := by simpa using hx    have hw' : w ≠ v := by simpa using hw    simp [hτ, Function.update_of_ne hx', Function.update_of_ne hw']  have hUS := maxcut_utility_sum_split G σ {v}  have hUT := maxcut_utility_sum_split G τ {v}  simp only [Finset.sum_singleton, SimpleGraph.irrefl, false_and, if_false] at hS hT hUS hUT  have hle : maxcut_utility G τ v ≤ maxcut_utility G σ v := by    have := hopt τ; omega  have hτu : maxcut_utility G τ v =      (Finset.univ.filter fun w => G.Adj v w ∧ σ w ≠ c).card := by    unfold maxcut_utility    congr 1    refine Finset.filter_congr fun w _ => ?_    by_cases hw : w = v    · subst hw; simp    · simp [hτ, Function.update_of_ne hw]  have h1 := Finset.card_filter_add_card_filter_not    (s := Finset.univ.filter fun w => G.Adj v w) (fun w => σ w = σ v)  have h2 := Finset.card_filter_add_card_filter_not    (s := Finset.univ.filter fun w => G.Adj v w) (fun w => σ w = c)  simp only [Finset.filter_filter] at h1 h2  rw [hτu] at hle  unfold maxcut_utility at hle  simp only [ne_eq] at hle h1 h2  omega
See it in the graphDiscuss this resultChallenge it