AFTD Auto-Formalizing Theoretical Domains

maxcut_utility_eq_sum

theoremverified

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.

  1. 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.

    line 4

    uses Finset.card_filter

      unfold 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

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]
See it in the graphDiscuss this resultChallenge it