maxcut_op89_exists_of_colorable
theoremverified
If 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 strong equilibrium; in particular OP-89 holds for every graph with χ(G) ≤ k, regardless of the number of vertices or of the maximum degree.
Statement
theorem maxcut_op89_exists_of_colorable {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hcol : G.Colorable k) : maxcut_has_optimal_strong_equilibrium G k
- Source
- step towards maxcut_op89_optimal_strong_equilibrium_exists
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
- maxcut_has_optimal_strong_equilibriumIn the unweighted Max-k-Cut game on a finite simple graph G with k colors, there exists an optimal coloring σ : V → Fin k that is also a…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
Lean source view module on GitHub
/-- OP-89 holds for every graph admitting a proper k-colouring (χ(G) ≤ k), with no bound on |V| or on the maximum degree. -/ theorem maxcut_op89_exists_of_colorable {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hcol : G.Colorable k) : maxcut_has_optimal_strong_equilibrium G k := by obtain ⟨σ⟩ := hcol have hprop : ∀ v w, G.Adj v w → σ.toFun v ≠ σ.toFun w := by intro v w hadj simpa using σ.map_rel hadj exact ⟨σ.toFun, maxcut_optimal_of_proper_coloring G σ.toFun hprop, maxcut_strong_equilibrium_of_proper_coloring G σ.toFun hprop⟩