AFTD Auto-Formalizing Theoretical Domains

maxcut_op89_exists_of_max_degree_le

theoremverifiedformalization

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

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.

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

    lines 3–4

      have hk1 : 1 ≤ k := by omega
      have : Nonempty (V → Fin k) := ⟨fun _ => ⟨0, hk1⟩⟩
  2. 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 σ.

    line 5

    uses Finite.exists_max

      obtain ⟨σ, hσ⟩ := Finite.exists_max (maxcut_welfare G (k := k))
  3. 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.

    line 6

    uses maxcut_optimal_strong_of_degree_le

      exact ⟨σ, 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

/-- 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σ⟩
See it in the graphDiscuss this resultChallenge it