AFTD Auto-Formalizing Theoretical Domains

chordal_maxcut_optimal_strong_equilibrium_of_card_le

theoremverifiedformalization

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.

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

    line 5

    uses maxcut_op89_exists_of_card_le_two_mul_add_one

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

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