maxcut_not_strong_equilibrium_top_three_constant
On the triangle with three colors, the constant coloring is not a strong equilibrium.
Statement
theorem maxcut_not_strong_equilibrium_top_three_constant :
¬ is_maxcut_strong_equilibrium (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 0, 0]- Source
- sanity check of is_maxcut_strong_equilibrium
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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_strong_deviation_top_three_constantOn the triangle with three colors, from the constant coloring the coalition of two vertices that recolor to the two other colors is a…
The proof, explained
The theorem is proved by contradiction. By definition, a strong equilibrium admits no profitable coalition deviation. We instantiate this condition with the explicit coalition deviation from `maxcut_strong_deviation_top_three_constant`, where vertices 1 and 2 switch to colors 1 and 2, yielding an immediate contradiction.
The constant coloring ![0, 0, 0] is not a strong equilibrium.
Assume for contradiction that the constant coloring is a strong equilibrium (h). By definition, a strong equilibrium admits no strong deviation by any coalition. Applying this assumption to the coalition S = {1, 2} and the deviation τ = ![0, 1, 2] contradicts `maxcut_strong_deviation_top_three_constant`, which proves that this pair is indeed a strong deviation.
uses
maxcut_strong_deviation_top_three_constantfun h => h _ _ maxcut_strong_deviation_top_three_constant
maxcut_strong_deviation_top_three_constant- In the complete graph on three vertices with three colors, the coalition {1, 2} deviating from the constant coloring ![0, 0, 0] to ![0, 1, 2] is a strong deviation.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem maxcut_not_strong_equilibrium_top_three_constant : ¬ is_maxcut_strong_equilibrium (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 0, 0] := fun h => h _ _ maxcut_strong_deviation_top_three_constant