maxcut_strong_equilibrium_exists_of_card_le
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.
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 σ.
uses
Finite.exists_maxhave : Nonempty (V → Fin k) := ⟨fun _ => ⟨0, hk⟩⟩ obtain ⟨σ, hσ⟩ := Finite.exists_max (maxcut_welfare G (k := k))
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.
uses
maxcut_optimal_strong_of_degree_lerefine ⟨σ, hσ, maxcut_optimal_strong_of_degree_le k hk V G (fun v => ?_) σ hσ⟩
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.
uses
G.degree_lt_card_vertshave := 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
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.
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