AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_of_proper_coloring

theoremverified

A 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 equals its full degree, and no colouring can give any player more than its degree.

Statement

theorem maxcut_optimal_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) : is_maxcut_optimal G σ
Source
step towards maxcut_op89_optimal_strong_equilibrium_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • maxcut_utility_of_proper_coloringIf σ 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 σ…
  • 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)…
  • is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
  • maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
  • maxcut_utility_le_degreeA player's utility in the Max-k-Cut game never exceeds its degree: the neighbours cut away by v form a subset of the neighbours of v.
Used by 1
  • maxcut_op89_exists_of_colorableIf a finite simple graph admits a proper k-colouring, then the unweighted Max-k-Cut game on (G,k) has an optimal colouring that is a…

Lean source view module on GitHub

/-- Any proper k-colouring is an optimal colouring of the Max-k-Cut game. -/
theorem maxcut_optimal_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) : is_maxcut_optimal G σ := by
  intro τ
  have hdeg : ∀ v, maxcut_utility G σ v = G.degree v :=
    fun v => maxcut_utility_of_proper_coloring G σ h v
  calc maxcut_welfare G τ = ∑ v, maxcut_utility G τ v := rfl
    _ ≤ ∑ v, G.degree v := Finset.sum_le_sum (fun v _ => maxcut_utility_le_degree G τ v)
    _ = ∑ v, maxcut_utility G σ v := Finset.sum_congr rfl (fun v _ => (hdeg v).symm)
    _ = maxcut_welfare G σ := rfl
See it in the graphDiscuss this resultChallenge it