AFTD Auto-Formalizing Theoretical Domains

maxcut_utility_color_permutation

theoremverified

Permuting all color labels preserves every player’s utility in the Max-k-Cut game.

Statement

theorem maxcut_utility_color_permutation {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ}
    (σ : V → Fin k) (p : Equiv.Perm (Fin k)) (v : V) :
    maxcut_utility G (fun w => p (σ w)) v = maxcut_utility G σ v
Source
Color-symmetry helper for the OP-89 pinned-twin refutation criterion.
Verified
25 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 4

The proof, explained

In the Max-k-Cut game, a vertex's utility is the number of its neighbors assigned a different color. Because any permutation of colors is a bijection, two vertices have distinct colors under the permuted coloring if and only if they have distinct colors under the original coloring. Consequently, the set of neighbors contributing to the utility of $v$ is unchanged, and its cardinality—the utility—is preserved.

  1. It suffices to show that the set of neighbors of $v$ with a different color than $v$ under $p \circ \sigma$ equals the corresponding set under $\sigma$.

    Unfolding the definition of `maxcut_utility`, the utility of $v$ is the cardinality of the finset of neighbors $w$ whose assigned color differs from that of $v$. By congruence (`congr 1`), equality of cardinalities reduces to proving that the two underlying sets of vertices are equal.

    lines 5–7

      classical
      unfold maxcut_utility
      congr 1
  2. The two sets of neighbors are equal, completing the proof.

    By extensionality (`ext w`), the two sets are equal if an arbitrary vertex $w$ belongs to the first if and only if it belongs to the second. For both sets, membership requires that $w$ is adjacent to $v$ and that the color of $w$ differs from the color of $v$. Because $p$ is a permutation, it is injective, so $p(\sigma(w)) \neq p(\sigma(v))$ is logically equivalent to $\sigma(w) \neq \sigma(v)$. The `simp` tactic applies this equivalence to simplify the membership conditions, leaving identical propositions on both sides and closing the goal.

    lines 8–9

      ext w
      simp

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_color_permutation {V : Type} [Fintype V]    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ}    (σ : V → Fin k) (p : Equiv.Perm (Fin k)) (v : V) :    maxcut_utility G (fun w => p (σ w)) v = maxcut_utility G σ v := by  classical  unfold maxcut_utility  congr 1  ext w  simp
See it in the graphDiscuss this resultChallenge it