AFTD Auto-Formalizing Theoretical Domains

maxcut_not_strong_equilibrium_top_three_constant

theoremverified

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

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.

  1. 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.

    line 3

    uses maxcut_strong_deviation_top_three_constant

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