maxcut_op89_exists_of_max_degree_five
For 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 coloring that is a strong equilibrium.
Statement
theorem maxcut_op89_exists_of_max_degree_five {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hk : 3 ≤ k) (hdeg : ∀ v, G.degree v ≤ 5) : maxcut_has_optimal_strong_equilibrium G k
- Formalizes
- arXiv:2610.04948 Cor. 9
- 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_op89_exists_of_max_degree_leFor 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…
Read back from the Lean
For any finite type $V$, any simple graph $G$ on $V$ with decidable adjacency, and any natural number $k \ge 3$, if every vertex $v \in V$ has degree at most 5 in $G$ ($G.\text{degree } v \le 5$), then there exists a configuration $\sigma : V \to \text{Fin } k$ that is simultaneously: 1. Welfare-optimal: for all configurations $\tau : V \to \text{Fin } k$, the total welfare $\sum_{v : V} \text{maxcut\_utility}(G, \tau, v)$ is less than or equal to $\sum_{v : V} \text{maxcut\_utility}(G, \sigma, v)$. 2. A strong equilibrium: for every finite subset $S \subseteq V$ and every configuration $\tau : V \to \text{Fin } k$, it is not the case that $S$ is nonempty, $\tau$ agrees with $\sigma$ outside $S$ ($\forall v \notin S, \tau(v) = \sigma(v)$), and every vertex in $S$ strictly improves its utility ($\forall v \in S, \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
The claim is reduced to the more general result `maxcut_op89_exists_of_max_degree_le`, which guarantees the existence of an optimal strong equilibrium whenever k ≥ 3 and every vertex has degree at most 2k - 1. Because k ≥ 3, we have 5 ≤ 2k - 1. Since every vertex degree is at most 5 by hypothesis, transitivity implies that every vertex degree is at most 2k - 1, completing the proof.
It suffices to show that every vertex in G has degree at most 2k - 1.
We apply the general theorem `maxcut_op89_exists_of_max_degree_le`, which guarantees that the Max-k-Cut game has an optimal strong equilibrium whenever k ≥ 3 and every vertex degree is bounded by 2k - 1.
uses
maxcut_op89_exists_of_max_degree_leapply maxcut_op89_exists_of_max_degree_le G k hkEvery vertex in G has degree at most 2k - 1.
Fix an arbitrary vertex v. Since k ≥ 3, elementary integer arithmetic gives 5 ≤ 2k - 1. Combining this with the assumption that the degree of v is at most 5 via transitivity (`le_trans`) establishes that the degree of v is at most 2k - 1.
uses
le_transintro v have : 5 ≤ 2 * k - 1 := by omega exact le_trans (hdeg v) this
maxcut_op89_exists_of_max_degree_le- In an unweighted Max-k-Cut game on a finite graph with k ≥ 3, if every vertex has degree at most 2k - 1, then there exists an optimal coloring that is a strong equilibrium.
le_trans- Transitivity of the ordering relation: if a ≤ b and b ≤ c, then a ≤ c.
- The arithmetic bound 5 ≤ 2k - 1 from k ≥ 3 on line 5 is discharged by the `omega` decision procedure.
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 5, then for every k ≥ 3 the Max-k-Cut game admits an optimal coloring that is a strong equilibrium. -/theorem maxcut_op89_exists_of_max_degree_five {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hk : 3 ≤ k) (hdeg : ∀ v, G.degree v ≤ 5) : maxcut_has_optimal_strong_equilibrium G k := by apply maxcut_op89_exists_of_max_degree_le G k hk intro v have : 5 ≤ 2 * k - 1 := by omega exact le_trans (hdeg v) this