AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_strong_of_color_unused

theoremverified

If σ is an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and some colour c is never used by σ, then σ is a strong equilibrium.

Statement

theorem maxcut_optimal_strong_of_color_unused {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : 0 < k) (σ : V → Fin k)
    (c : Fin k) (hc : ∀ v, σ v ≠ c) (hopt : is_maxcut_optimal G σ) :
    is_maxcut_strong_equilibrium G σ
Source
step towards maxcut_op89_optimal_strong_equilibrium_exists
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • maxcut_optimal_same_color_leAt an optimal coloring σ of the Max-k-Cut game, for every vertex v and every color c, the number of neighbours of v with color σ(v) is at…
  • maxcut_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
  • 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.
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
  • 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).
  • 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…

Lean source view module on GitHub

/-- An optimal colouring that leaves a colour unused is automatically a strong equilibrium. -/
theorem maxcut_optimal_strong_of_color_unused {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : 0 < k) (σ : V → Fin k)
    (c : Fin k) (hc : ∀ v, σ v ≠ c) (hopt : is_maxcut_optimal G σ) :
    is_maxcut_strong_equilibrium G σ := by
  intro S τ hdev
  rcases hdev with ⟨hne, -, hstrict⟩
  obtain ⟨v, hv⟩ := hne
  have h_c_empty : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c) = ∅ := by
    rw [Finset.filter_eq_empty_iff]
    intro w _ hw
    exact hc w hw.2
  have h_same_le := maxcut_optimal_same_color_le G σ hopt v c
  rw [h_c_empty, Finset.card_empty] at h_same_le
  have h_add := maxcut_utility_add_monochromatic_card G σ v
  have h_tau_le := maxcut_utility_le_degree G τ v
  have hlt := hstrict v hv
  omega
See it in the graphDiscuss this resultChallenge it