AFTD Auto-Formalizing Theoretical Domains

chordal_maxcut_optimal_strong_equilibrium_of_max_degree_le

theoremverifiedformalization

For every finite simple chordal graph G whose maximum degree is at most 2k - 1 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_max_degree_le
    {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ)
    (hchord : is_chordal G) (hk : 3 ≤ k) (hdeg : ∀ v, G.degree 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_max_degree_leFor every integer k ≥ 3 and every finite simple graph G whose maximum degree is at most 2k - 1, the unweighted Max-k-Cut game admits an…

Read back from the Lean

Let $V$ be a finite type, $G$ be a simple graph on $V$ with decidable adjacency relation, and $k$ be a natural number. Assume: 1. hchord: $G$ is chordal (is_chordal G), defined as: for all $n \in \mathbb{N}$ with $4 \le n$, the cycle graph on $n$ vertices is not an induced subgraph of $G$ (¬ SimpleGraph.IsIndContained (SimpleGraph.cycleGraph n) G). 2. hk: $3 \le k$. 3. hdeg: For all $v \in V$, the degree of $v$ in $G$ is at most $2k - 1$ (G.degree v ≤ 2 * k - 1). Then $G$ and $k$ admit an optimal strong equilibrium for max-cut (maxcut_has_optimal_strong_equilibrium G k), which asserts the existence of a configuration $\sigma : V \to \text{Fin } k$ such that: 1. $\sigma$ is welfare-optimal (is_maxcut_optimal G σ): for every configuration $\tau : V \to \text{Fin } k$, the total welfare of $\tau$ is at most that of $\sigma$ ($\sum_{v \in V} \text{maxcut\_utility}(G, \tau, v) \le \sum_{v \in V} \text{maxcut\_utility}(G, \sigma, v)$); and 2. $\sigma$ is a strong equilibrium (is_maxcut_strong_equilibrium G σ): there is no nonempty coalition $S \subseteq V$ and deviation $\tau : V \to \text{Fin } k$ with $\tau(v) = \sigma(v)$ for all $v \notin S$ such that every $v \in S$ strictly improves its utility ($\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 theorem is proved directly as a corollary of the more general theorem `maxcut_op89_exists_of_max_degree_le`, which guarantees an optimal strong equilibrium for the Max-$k$-Cut game on any finite simple graph with maximum degree at most $2k - 1$ whenever $k \ge 3$. Supplying the graph $G$, the inequality $3 \le k$, and the degree hypothesis immediately concludes the proof, leaving the chordality assumption unused.

  1. The graph $G$ admits an optimal strong equilibrium in the Max-$k$-Cut game.

    Apply the theorem `maxcut_op89_exists_of_max_degree_le` directly with graph $G$, integer $k$, the condition $k \ge 3$ (`hk`), and the degree bound $\forall v, \deg(v) \le 2k - 1$ (`hdeg`). The chordality hypothesis (`hchord`) is not needed.

    line 5

    uses maxcut_op89_exists_of_max_degree_le

        maxcut_has_optimal_strong_equilibrium G k := maxcut_op89_exists_of_max_degree_le G k hk hdeg
maxcut_op89_exists_of_max_degree_le
For any finite simple graph with maximum degree at most $2k - 1$ where $k \ge 3$, the unweighted Max-$k$-Cut game admits an optimal configuration that is also a strong equilibrium.

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 with maximum degree at most 2k - 1, the Max-k-Cut game has an optimal strong equilibrium. -/theorem chordal_maxcut_optimal_strong_equilibrium_of_max_degree_le    {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ)    (hchord : is_chordal G) (hk : 3 ≤ k) (hdeg : ∀ v, G.degree v ≤ 2 * k - 1) :    maxcut_has_optimal_strong_equilibrium G k := maxcut_op89_exists_of_max_degree_le G k hk hdeg
See it in the graphDiscuss this resultChallenge it