chordal_maxcut_optimal_strong_equilibrium_of_max_degree_le
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.
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.
uses
maxcut_op89_exists_of_max_degree_lemaxcut_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.
- The hypothesis `hchord` (that $G$ is chordal) is completely unused in the proof. The theorem is a direct specialization of a more general result that holds for any finite simple graph.
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