maxcut_utility_sum_split
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
- maxcut_deviation_cross_mono_riseLet σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then…
- maxcut_defect_two_deviation_welfare_nondecreasingA strong deviation cannot decrease the cut value when every member of the deviating coalition initially has at most two same-colored…
- maxcut_optimal_no_clique_deviationIn the unweighted Max-k-Cut game on a finite simple graph, no coalition that induces a clique has a strong deviation from a…
- maxcut_two_color_strong_equilibrium_restricts_vertexFor every finite graph and every vertex, a strong two-color equilibrium exists whose restriction after deleting that vertex is also…
- maxcut_deviation_mono_inside_dropLet σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then…
- maxcut_defect_two_equal_welfare_deviation_structureIf a strong deviation from coalition defect at most two preserves welfare, every deviator has defect two before and one after, every old…
- maxcut_optimal_strong_of_degree_leFor 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…
- 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…
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ᶜ.
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.
uses
maxcut_utility_eq_sum,Finset.sum_add_distribsimp only [maxcut_utility_eq_sum, ← Finset.sum_add_distrib]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.
uses
Finset.sum_congr,Finset.sum_add_sum_complexact 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
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_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