AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_exists_of_card_le

theoremverifiedoriginal

For 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 equilibrium; in particular, for k ≥ 3, every graph on at most 6 vertices has a strong equilibrium.

Statement

theorem maxcut_strong_equilibrium_exists_of_card_le (V : Type) [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (k : ℕ) (hk : 1 ≤ k) (hV : Fintype.card V ≤ 2 * k) :
    ∃ σ : V → Fin k, is_maxcut_optimal G σ ∧ is_maxcut_strong_equilibrium G σ
Related work
special case of the existence question of arXiv:2610.04948, Sec. 4 (does every unweighted Max-k-Cut game admit a strong equilibrium?); immediate from that paper's Corollary 9, since a graph on at most 2k vertices has maximum degree at most 2k − 1
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • 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.
  • 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.
Used by 1
  • maxcut_op89_exists_of_card_leFor every integer k ≥ 3, every finite simple graph on at most 2k vertices admits an optimal coloring that is a strong equilibrium in the…

The proof, explained

To find a strong equilibrium, the proof selects a coloring σ that maximizes total cut welfare, which exists because the configuration space of colorings is finite and nonempty. By a known result (maxcut_optimal_strong_of_degree_le), any welfare-optimal coloring is a strong equilibrium provided all vertex degrees are at most 2k - 1. In a simple graph on at most 2k vertices, each vertex degree is strictly less than the vertex count, hence at most 2k - 1, which completes the argument.

  1. There exists a coloring σ : V → Fin k that maximizes the Max-k-Cut welfare.

    Because k ≥ 1, the space of colorings V → Fin k is nonempty (for instance, by assigning 0 to every vertex). Since V is finite, the space of colorings is finite, so by Finite.exists_max, the social welfare function attains a maximum at some coloring σ.

    lines 4–5

    uses Finite.exists_max

      have : Nonempty (V → Fin k) := ⟨fun _ => ⟨0, hk⟩⟩
      obtain ⟨σ, hσ⟩ := Finite.exists_max (maxcut_welfare G (k := k))
  2. The welfare-optimal coloring σ is a strong equilibrium provided every vertex degree is at most 2k - 1.

    Providing σ and its welfare optimality hσ as witnesses, we invoke maxcut_optimal_strong_of_degree_le, which guarantees that an optimal coloring is a strong equilibrium as long as every vertex v satisfies degree(v) ≤ 2k - 1. This leaves the degree bound for an arbitrary vertex v as the remaining goal.

    line 6

    uses maxcut_optimal_strong_of_degree_le

      refine ⟨σ, hσ, maxcut_optimal_strong_of_degree_le k hk V G (fun v => ?_) σ hσ⟩
  3. Every vertex v has degree at most 2k - 1.

    For any vertex v, G.degree_lt_card_verts provides the strict inequality degree(v) < |V|. Since |V| ≤ 2k by assumption, linear integer arithmetic (omega) closes the goal by deducing degree(v) ≤ 2k - 1.

    lines 7–8

    uses G.degree_lt_card_verts

      have := G.degree_lt_card_verts v
      omega
Finite.exists_max
A function from a nonempty finite type to a linearly ordered type attains its maximum value.
maxcut_optimal_strong_of_degree_le
For k ≥ 1, in any graph where every vertex has degree at most 2k - 1, every welfare-optimal k-cut coloring is a strong equilibrium.
G.degree_lt_card_verts
In any finite simple graph, the degree of every vertex is strictly less than the total number of vertices.

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

theorem maxcut_strong_equilibrium_exists_of_card_le (V : Type) [Fintype V] (G : SimpleGraph V)    [DecidableRel G.Adj] (k : ℕ) (hk : 1 ≤ k) (hV : Fintype.card V ≤ 2 * k) :    ∃ σ : V → Fin k, is_maxcut_optimal G σ ∧ is_maxcut_strong_equilibrium G σ := by  have : Nonempty (V → Fin k) := ⟨fun _ => ⟨0, hk⟩⟩  obtain ⟨σ, hσ⟩ := Finite.exists_max (maxcut_welfare G (k := k))  refine ⟨σ, hσ, maxcut_optimal_strong_of_degree_le k hk V G (fun v => ?_) σ hσ⟩  have := G.degree_lt_card_verts v  omega
See it in the graphDiscuss this resultChallenge it