maxcut_op89_exists_of_card_le
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
- 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…
- maxcut_strong_equilibrium_exists_of_card_leFor every k ≥ 1 and every finite simple graph on at most 2k vertices, the Max-k-Cut game has an optimal coloring that is a strong…
- Used by 1
- maxcut_op89_exists_of_card_le_two_mul_add_oneFor every integer k ≥ 3 and every finite simple graph G on at most 2k+1 vertices, the unweighted Max-k-Cut game on (G,k) admits an optimal…
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.
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`).
uses
maxcut_strong_equilibrium_exists_of_card_leexact 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
- The goal `maxcut_has_optimal_strong_equilibrium G k` is definitionally equal to the existential statement `∃ σ, is_maxcut_optimal G σ ∧ is_maxcut_strong_equilibrium G σ` produced by `maxcut_strong_equilibrium_exists_of_card_le`, so no unfolding is required.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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