AFTD Auto-Formalizing Theoretical Domains

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⟩
See it in the graphDiscuss this resultChallenge it