AFTD Auto-Formalizing Theoretical Domains

maxcut_op89_optimal_strong_equilibrium_negation

theoremverifiedoriginal

It is not true that for every finite type V, simple graph G on V with decidable adjacency, and k ≥ 3, the unweighted Max-k-Cut game on G has an optimal coloring that is a strong equilibrium (the negation of maxcut_op89_optimal_strong_equilibrium_exists); the 182-vertex pinned twins graph with k = 3 is a counterexample.

Statement

theorem maxcut_op89_optimal_strong_equilibrium_negation :
    ¬ ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ),
      3 ≤ k → maxcut_has_optimal_strong_equilibrium G k
Related work
arXiv:2610.04948, Section 4 (concluding remarks), Question 2 (OP-89): does every unweighted Max-k-Cut game admit an optimal coloring that is a strong equilibrium? Answered negatively for k = 3 by the pinned twins graph.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_pinned_twins_optimum_rigidityEvery welfare-maximizing 3-coloring ρ of the 182-vertex pinned twins graph maxcut_pinned_twins_graph is, up to one global permutation p of…
  • maxcut_pinned_twins_refutes_of_rigidityIf every optimum of the explicit pinned-twin graph is its displayed initial coloring up to a global color permutation, then this graph has…
  • maxcut_pinned_twins_graphA candidate counterexample graph on 182 vertices. Replace each vertex of the paper graph G_3 by two independent twins, replace each old…
  • 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…

Read back from the Lean

The theorem asserts the negation of the following statement: for every finite type V, every simple graph G on V with decidable adjacency, and every natural number k ≥ 3, there exists an assignment σ : V → Fin k that is both: 1. Max-cut optimal: for all assignments τ : V → Fin k, the welfare under τ (defined as ∑ v, maxcut_utility G τ v) is less than or equal to the welfare under σ. 2. A max-cut strong equilibrium: for every non-empty finite subset S of V and every assignment τ : V → Fin k that agrees with σ outside S (i.e., ∀ v ∉ S, τ v = σ v), it is not the case that every vertex v ∈ S strictly increases its utility (maxcut_utility G σ v < maxcut_utility G τ v).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by contradiction using the 182-vertex pinned twins graph at k = 3 as an explicit counterexample. Assuming every graph has an optimal strong equilibrium for k ≥ 3, specializing to this graph produces an optimal 3-coloring that is also a strong equilibrium. However, the optimum rigidity theorem shows all optimal 3-colorings on this graph are unique up to permutation, and this rigidity rules out being a strong equilibrium. This contradiction disproves the universal claim.

  1. Adjacency in the pinned twins graph is decidable. automation

    Unfolding the definition of `maxcut_pinned_twins_graph` reveals it as a simple graph constructed from the relation `MaxcutPinnedTwins.rel`. Typeclass inference automatically synthesizes the decidability of its adjacency relation from the decidability of that relation.

    lines 1–4

    private instance maxcut_op89_optimal_strong_equilibrium_negation_dec :
        DecidableRel maxcut_pinned_twins_graph.Adj := by
      unfold maxcut_pinned_twins_graph
      infer_instance
  2. The universal claim fails, as the 182-vertex pinned twins graph with k = 3 admits no optimal strong equilibrium.

    Assume for contradiction that every graph admits an optimal strong equilibrium for all k ≥ 3 (hypothesis h). Specializing this assumption to the pinned twins graph and k = 3 (with 3 ≤ 3 supplied by le_rfl) produces an optimal strong equilibrium. However, maxcut_pinned_twins_optimum_rigidity proves that every optimal 3-coloring of this graph is rigid (unique up to color permutations), and maxcut_pinned_twins_refutes_of_rigidity proves that this rigidity prevents any such coloring from being a strong equilibrium. This contradiction completes the proof.

    lines 6–9

    uses maxcut_pinned_twins_refutes_of_rigidity, maxcut_pinned_twins_optimum_rigidity, le_rfl

    theorem maxcut_op89_optimal_strong_equilibrium_negation :
        ¬ ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ),
          3 ≤ k → maxcut_has_optimal_strong_equilibrium G k := fun h => maxcut_pinned_twins_refutes_of_rigidity maxcut_pinned_twins_optimum_rigidity
      (h _ maxcut_pinned_twins_graph 3 le_rfl)
maxcut_pinned_twins_optimum_rigidity
Every welfare-optimal 3-coloring of the pinned twins graph is rigid, coinciding with the canonical initial coloring up to a permutation of the three colors.
maxcut_pinned_twins_refutes_of_rigidity
If all welfare-optimal 3-colorings of the pinned twins graph are rigid, then the graph does not admit any optimal strong equilibrium for k = 3.
le_rfl
Any element in a preorder is less than or equal to itself (here, 3 ≤ 3).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

private instance maxcut_op89_optimal_strong_equilibrium_negation_dec :    DecidableRel maxcut_pinned_twins_graph.Adj := by  unfold maxcut_pinned_twins_graph  infer_instancetheorem maxcut_op89_optimal_strong_equilibrium_negation :    ¬ ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ),      3 ≤ k → maxcut_has_optimal_strong_equilibrium G k := fun h => maxcut_pinned_twins_refutes_of_rigidity maxcut_pinned_twins_optimum_rigidity  (h _ maxcut_pinned_twins_graph 3 le_rfl)
See it in the graphDiscuss this resultChallenge it