AFTD Auto-Formalizing Theoretical Domains

maxcut_op89_exists_of_max_degree_five

theoremverifiedformalization

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

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.

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

    line 3

    uses maxcut_op89_exists_of_max_degree_le

      apply maxcut_op89_exists_of_max_degree_le G k hk
  2. Every 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.

    lines 4–6

    uses le_trans

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

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