chordal_maxcut_optimal_strong_equilibrium_of_card_le
For every finite simple chordal graph G on at most 2k + 1 vertices and every integer k ≥ 3, the unweighted Max-k-Cut game admits an optimal coloring that is a strong equilibrium.
Statement
theorem chordal_maxcut_optimal_strong_equilibrium_of_card_le {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hchord : is_chordal G) (hk : 3 ≤ k) (hV : Fintype.card V ≤ 2 * k + 1) : maxcut_has_optimal_strong_equilibrium G k
- Formalizes
- arXiv:2610.04948
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_chordalA simple graph G is chordal if it contains no induced cycle of length four or greater.
- 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_card_le_two_mul_add_oneFor every integer k ≥ 3 and every finite simple graph G on at most 2k+1 vertices, the unweighted Max-k-Cut game on (G,k) admits an optimal…
Read back from the Lean
For any finite type V with a simple graph G on V having decidable adjacency, and any natural number k:
if G is chordal (i.e., for every natural number n ≥ 4, G contains no induced subgraph isomorphic to the cycle graph of length n),
3 ≤ k,
and the number of vertices in V is at most 2 * k + 1,
then G has an optimal strong equilibrium with k strategies: that is, there exists a strategy assignment σ : V → Fin k that is simultaneously:
1. Max-cut optimal (its max-cut welfare is at least that of any other assignment τ : V → Fin k), and
2. A max-cut strong equilibrium (no non-empty coalition of vertices S ⊆ V has a strong deviation τ : V → Fin k agreeing with σ outside S where every vertex in S strictly improves its utility).
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 theorem establishes that the Max-k-Cut game on a chordal graph on at most 2k + 1 vertices has an optimal strong equilibrium for k ≥ 3. The proof is immediate: it invokes a stronger theorem, `maxcut_op89_exists_of_card_le_two_mul_add_one`, which proves the same existence claim for arbitrary finite simple graphs without requiring chordality.
The Max-k-Cut game on G has an optimal strong equilibrium.
The theorem follows directly by applying `maxcut_op89_exists_of_card_le_two_mul_add_one` to the graph G and parameters k, using the hypotheses hk (3 ≤ k) and hV (|V| ≤ 2k + 1). The assumption that G is chordal is not needed.
uses
maxcut_op89_exists_of_card_le_two_mul_add_onemaxcut_has_optimal_strong_equilibrium G k := maxcut_op89_exists_of_card_le_two_mul_add_one G k hk hV
maxcut_op89_exists_of_card_le_two_mul_add_one- Every finite simple graph with at most 2k + 1 vertices admits an optimal strong equilibrium for the Max-k-Cut game when k ≥ 3.
- The chordality assumption `hchord` is unused in the proof; the result holds for any finite simple graph satisfying the vertex count bound.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- For any finite simple chordal graph on at most 2k + 1 vertices, the Max-k-Cut game has an optimal strong equilibrium. -/theorem chordal_maxcut_optimal_strong_equilibrium_of_card_le {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hchord : is_chordal G) (hk : 3 ≤ k) (hV : Fintype.card V ≤ 2 * k + 1) : maxcut_has_optimal_strong_equilibrium G k := maxcut_op89_exists_of_card_le_two_mul_add_one G k hk hV