AFTD Auto-Formalizing Theoretical Domains

maxcut_utility_sum_split

theoremverified

For 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 to its complement.

Statement

theorem maxcut_utility_sum_split {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    {k : ℕ} (ρ : V → Fin k) (S : Finset V) :
    ∑ v ∈ S, maxcut_utility G ρ v =
      ∑ 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 : ℕ)
Source
step towards maxcut_optimal_strong_of_degree_le (arXiv:2610.04948, Corollary 9)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • maxcut_utility_eq_sumThe Max-k-Cut utility of v is the sum over all w of the indicator that w is a neighbour of v with a different color.
  • 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 total utility of vertices in S is the sum over v ∈ S of the bichromatic neighbors of v in the entire graph. The proof rewrites each vertex's utility as a sum over all vertices w and combines the two summations on the right-hand side into a single outer sum over v ∈ S. It then concludes by decomposing the inner sum over all vertices into the sum over w ∈ S and the sum over w ∈ Sᶜ.

  1. The total utility over S is expressed as an outer sum over v ∈ S of an inner sum over all w ∈ V, while the right-hand side is combined into a single outer sum over v ∈ S of the two inner sums.

    Using maxcut_utility_eq_sum, each maxcut_utility G ρ v on the left-hand side is expanded into a sum over all vertices w ∈ V of the indicator that w is adjacent to v with a different color. On the right-hand side, the two separate sums over v ∈ S are combined into a single sum over v ∈ S using the distributivity of summation (Finset.sum_add_distrib) in reverse.

    line 6

    uses maxcut_utility_eq_sum, Finset.sum_add_distrib

      simp only [maxcut_utility_eq_sum, ← Finset.sum_add_distrib]
  2. The equality holds: the total utility on S splits into the internal and boundary cut contributions.

    By Finset.sum_congr, since the outer sums both run over v ∈ S, it suffices to show that their inner summands agree for each v. For a fixed v, Finset.sum_add_sum_compl states that the sum over w ∈ S plus the sum over w ∈ Sᶜ equals the sum over all vertices w in the whole vertex set V. Applying its symmetry closes the goal.

    line 7

    uses Finset.sum_congr, Finset.sum_add_sum_compl

      exact Finset.sum_congr rfl fun v _ => (Finset.sum_add_sum_compl S _).symm
maxcut_utility_eq_sum
The Max-Cut utility of a vertex v equals the sum over all vertices w of 1 if v and w are adjacent and have different colors under ρ, and 0 otherwise.
Finset.sum_add_distrib
The sum of a pointwise sum f(x) + g(x) over a finite set equals the sum of f(x) plus the sum of g(x).
Finset.sum_congr
Two sums over finite sets are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.sum_add_sum_compl
For any subset s of a finite type, the sum of a function over s plus its sum over the complement sᶜ equals the sum of the function over the entire type.

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_utility_sum_split {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    {k : ℕ} (ρ : V → Fin k) (S : Finset V) :    ∑ v ∈ S, maxcut_utility G ρ v =      ∑ 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 : ℕ) := by  simp only [maxcut_utility_eq_sum, ← Finset.sum_add_distrib]  exact Finset.sum_congr rfl fun v _ => (Finset.sum_add_sum_compl S _).symm
See it in the graphDiscuss this resultChallenge it