AFTD Auto-Formalizing Theoretical Domains

maxcut_utility_of_proper_coloring

theoremverified

If σ is a proper k-colouring of a finite simple graph G, then each player v has Max-k-Cut utility equal to its degree: maxcut_utility G σ v = G.degree v.

Statement

theorem maxcut_utility_of_proper_coloring {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (h : ∀ v w, G.Adj v w → σ v ≠ σ w) (v : V) : maxcut_utility G σ v = G.degree v
Source
step towards maxcut_op89_optimal_strong_equilibrium_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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)…
  • maxcut_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
Used by 3

Lean source view module on GitHub

/-- At any proper k-colouring of a graph G, every player v achieves maximal possible utility equal to its degree G.degree v, because it has zero monochromatic neighbours. -/
theorem maxcut_utility_of_proper_coloring {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (h : ∀ v w, G.Adj v w → σ v ≠ σ w) (v : V) : maxcut_utility G σ v = G.degree v := by
  have hsum := maxcut_utility_add_monochromatic_card G σ v
  have hempty : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v) = ∅ := by
    apply Finset.filter_false_of_mem
    intro w _ hw
    exact h v w hw.1 hw.2.symm
  rw [hempty] at hsum
  simp at hsum
  exact hsum
See it in the graphDiscuss this resultChallenge it