AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_of_proper_coloring

theoremverified

A 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 degree, so no coalition can make any of its members strictly better off.

Statement

theorem maxcut_strong_equilibrium_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_strong_equilibrium 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 σ…
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
  • is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
  • 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_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 2

Lean source view module on GitHub

/-- Any proper k-colouring is a strong equilibrium of the Max-k-Cut game. -/
theorem maxcut_strong_equilibrium_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_strong_equilibrium G σ := by
  intro S τ hdev
  obtain ⟨hne, -, himp⟩ := hdev
  obtain ⟨v, hv⟩ := hne
  have h1 := himp v hv
  have h2 : maxcut_utility G σ v = G.degree v :=
    maxcut_utility_of_proper_coloring G σ h v
  have h3 := maxcut_utility_le_degree G τ v
  omega
See it in the graphDiscuss this resultChallenge it