maxcut_op89_exists_of_max_degree_le
For every integer k ≥ 3 and every finite simple graph G whose maximum degree is at most 2k - 1, the unweighted Max-k-Cut game admits an optimal coloring that is a strong equilibrium (arXiv:2610.04948, Corollary 9).
Statement
theorem maxcut_op89_exists_of_max_degree_le {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hk : 3 ≤ k) (hdeg : ∀ v, G.degree v ≤ 2 * k - 1) : maxcut_has_optimal_strong_equilibrium G k
- Formalizes
- arXiv:2610.04948 Cor. 9
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_optimal_strong_of_degree_leFor every k ≥ 1: on every finite simple graph whose maximum degree is at most 2k − 1, every optimal coloring of the unweighted Max-k-Cut…
- maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- Used by 3
- maxcut_op89_exists_of_max_degree_fiveFor every integer k ≥ 3 and every finite simple graph G whose maximum degree is at most 5, the unweighted Max-k-Cut game admits an optimal…
- maxcut_strong_equilibrium_reduce_dense_coreFix k at least three. If every finite graph of minimum degree at least k, with preconnected vertex deletions and with some vertex of…
- chordal_maxcut_optimal_strong_equilibrium_of_max_degree_leFor every finite simple chordal graph G whose maximum degree is at most 2k - 1 and every integer k ≥ 3, the unweighted Max-k-Cut game…
Read back from the Lean
Let $V$ be a finite type, $G$ be a simple graph on $V$ with decidable adjacency, and $k$ be a natural number such that $3 \le k$. Assume that every vertex $v \in V$ has degree at most $2k - 1$ (i.e. $G.\text{degree}(v) \le 2k - 1$). Then there exists a coloring/assignment $\sigma : V \to \text{Fin } k$ that is simultaneously maxcut-optimal (its total welfare $\sum_{v} \text{maxcut\_utility}(G, \sigma, v)$ is at least that of any other assignment $\tau : V \to \text{Fin } k$) and a maxcut strong equilibrium (there is no non-empty coalition of vertices $S \subseteq V$ and assignment $\tau : V \to \text{Fin } k$ agreeing with $\sigma$ outside $S$ such that every vertex $v \in S$ strictly increases its utility, $\text{maxcut\_utility}(G, \sigma, v) < \text{maxcut\_utility}(G, \tau, 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
To prove that an optimal strong equilibrium exists, the argument takes a k-coloring that maximizes total welfare (the cut size) and invokes an established theorem showing that whenever the maximum degree is at most 2k - 1, every welfare-maximizing coloring is automatically a strong equilibrium. Since k ≥ 3 ≥ 1 and the vertex set is finite, the space of colorings is finite and nonempty, guaranteeing the existence of such a maximum.
The space of k-colorings V → Fin k is nonempty.
Since k ≥ 3, linear integer arithmetic gives k ≥ 1. Thus 0 is a valid color in Fin k, and the constant coloring assigning color 0 to every vertex witnesses that V → Fin k is nonempty.
have hk1 : 1 ≤ k := by omega have : Nonempty (V → Fin k) := ⟨fun _ => ⟨0, hk1⟩⟩
There exists a coloring σ : V → Fin k that maximizes the Max-Cut welfare.
Because V and Fin k are finite, the function space V → Fin k is finite. As it is also nonempty, Finite.exists_max implies that the welfare function maxcut_welfare G achieves its maximum at some coloring σ.
uses
Finite.exists_maxobtain ⟨σ, hσ⟩ := Finite.exists_max (maxcut_welfare G (k := k))The coloring σ is an optimal strong equilibrium, completing the proof.
By definition, σ is an optimal coloring since it maximizes welfare. Furthermore, by maxcut_optimal_strong_of_degree_le, in any graph where every vertex has degree at most 2k - 1, any welfare-maximizing coloring is necessarily a strong equilibrium. Hence σ is both optimal and a strong equilibrium.
uses
maxcut_optimal_strong_of_degree_leexact ⟨σ, hσ, maxcut_optimal_strong_of_degree_le k hk1 V G hdeg σ hσ⟩
Finite.exists_max- Every function from a nonempty finite type to a linearly ordered type attains a maximum value.
maxcut_optimal_strong_of_degree_le- For any k ≥ 1, in every finite graph with maximum degree at most 2k - 1, every welfare-maximizing k-coloring is 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
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: if the maximum degree is at most 2k - 1, then the Max-k-Cut game admits an optimal coloring that is a strong equilibrium. -/theorem maxcut_op89_exists_of_max_degree_le {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hk : 3 ≤ k) (hdeg : ∀ v, G.degree v ≤ 2 * k - 1) : maxcut_has_optimal_strong_equilibrium G k := by have hk1 : 1 ≤ k := by omega have : Nonempty (V → Fin k) := ⟨fun _ => ⟨0, hk1⟩⟩ obtain ⟨σ, hσ⟩ := Finite.exists_max (maxcut_welfare G (k := k)) exact ⟨σ, hσ, maxcut_optimal_strong_of_degree_le k hk1 V G hdeg σ hσ⟩