maxcut_utility_eq_sum
The 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.
Statement
theorem maxcut_utility_eq_sum {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (ρ : V → Fin k) (v : V) : maxcut_utility G ρ v = ∑ w, 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 1
- 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 3
- 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_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_anchor_neutral_pivot_initial_optimalThe initial profile remains globally optimal after the extra edge is added.
The proof, explained
The Max-k-Cut utility of a vertex v is defined as the number of vertices that are neighbors of v with a different color. Unfolding this definition gives the cardinality of a filtered set of vertices. Applying Finset.card_filter immediately rewrites this cardinality as the sum of indicator functions over all vertices.
maxcut_utility G ρ v = ∑ w, if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0
Unfolding the definition of maxcut_utility expresses the utility as the cardinality of the filtered finset of vertices w such that G.Adj v w ∧ ρ w ≠ ρ v. Rewriting with Finset.card_filter converts the cardinality of this filtered set into the sum over all vertices w of the indicator that w is a neighbor of v with a different color.
uses
Finset.card_filterunfold maxcut_utility; rw [Finset.card_filter]
Finset.card_filter- The cardinality of a filtered finite set {x ∈ s | p x} equals the sum over x ∈ s of the indicator function evaluating to 1 when p x is true and 0 otherwise.
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_eq_sum {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (ρ : V → Fin k) (v : V) : maxcut_utility G ρ v = ∑ w, if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 := by unfold maxcut_utility; rw [Finset.card_filter]