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
- 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…
- 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
/-- 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