AFTD Auto-Formalizing Theoretical Domains

maxcut_op89_exists_of_card_le

theoremverifiedformalization

For every integer k ≥ 3, every finite simple graph on at most 2k vertices admits an optimal coloring that is a strong equilibrium in the unweighted Max-k-Cut game.

Statement

theorem maxcut_op89_exists_of_card_le (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hk : 3 ≤ k) (hV : Fintype.card V ≤ 2 * k) : maxcut_has_optimal_strong_equilibrium G k
Formalizes
arXiv:2610.04948 Sec. 3; folklore
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

Read back from the Lean

For every finite type V, every simple graph G on V with decidable adjacency, and every natural number k, if 3 ≤ k and the cardinality of V is at most 2 * k, then there exists an assignment σ : V → Fin k that is both maxcut-optimal (its welfare maxcut_welfare G σ is at least maxcut_welfare G τ for all τ : V → Fin k) and a strong equilibrium (there is no nonempty coalition S : Finset V and deviation τ : V → Fin k coinciding with σ outside S such that every vertex in S strictly improves its utility maxcut_utility).

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 result is a direct specialization of `maxcut_strong_equilibrium_exists_of_card_le`, which guarantees that every finite graph with at most 2k vertices admits an optimal k-coloring that is a strong equilibrium whenever k ≥ 1. Since the hypothesis assumes k ≥ 3, the condition k ≥ 1 is satisfied immediately by linear integer arithmetic.

  1. There exists an optimal coloring for G that is a strong equilibrium in the unweighted Max-k-Cut game.

    We apply the general theorem `maxcut_strong_equilibrium_exists_of_card_le`, which guarantees such a coloring exists as long as |V| ≤ 2k and 1 ≤ k. The vertex bound |V| ≤ 2k is given by hypothesis `hV`, and the condition 1 ≤ k follows immediately from k ≥ 3 by linear arithmetic (`omega`).

    line 3

    uses maxcut_strong_equilibrium_exists_of_card_le

      exact maxcut_strong_equilibrium_exists_of_card_le V G k (by omega) hV
maxcut_strong_equilibrium_exists_of_card_le
for every finite graph with at most 2k vertices and every integer k ≥ 1, there exists a k-coloring that is both Max-Cut optimal and a strong equilibrium

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

/-- Partial result for OP-89: every graph on at most 2k vertices admits an optimal coloring that is a strong equilibrium. -/theorem maxcut_op89_exists_of_card_le (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hk : 3 ≤ k) (hV : Fintype.card V ≤ 2 * k) : maxcut_has_optimal_strong_equilibrium G k := by  exact maxcut_strong_equilibrium_exists_of_card_le V G k (by omega) hV
See it in the graphDiscuss this resultChallenge it