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
- maxcut_optimal_of_proper_coloringA proper k-colouring of a finite simple graph is a maximum k-cut of the Max-k-Cut game: it cuts every edge, so each player's utility…
- maxcut_strong_equilibrium_of_proper_coloringA proper k-colouring of a finite simple graph is a strong equilibrium of the Max-k-Cut game: every player already has utility equal to its…
- maxcut_unused_color_or_safe_pivot_of_proper_coloringIf a finite graph admits a proper k-coloring and N has fewer than 2k vertices, there is a strong equilibrium with an unused color on N or…
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