maxcut_strong_equilibrium_reduce_dense_core
Fix k at least three. If every finite graph of minimum degree at least k, with preconnected vertex deletions and with some vertex of degree at least 2k, has a strong k-color equilibrium, then every finite graph has a strong k-color equilibrium.
Statement
theorem maxcut_strong_equilibrium_reduce_dense_core (k : ℕ) (hk : 3 ≤ k) (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], (∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected) → (∀ v : V, k ≤ G.degree v) → (∃ v : V, 2 * k ≤ G.degree v) → ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ) : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ
- Source
- Structural reduction for OP-85, the unweighted Max-k-Cut strong-equilibrium existence question in arXiv:2610.04948, Section 4.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- maxcut_strong_equilibrium_reduce_connected_coreFix k. If every finite graph of minimum degree at least k whose every vertex deletion is preconnected has a strong k-color equilibrium,…
- 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…
- 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…
- 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.
The proof, explained
The proof reduces the existence of strong k-color equilibria on arbitrary finite graphs to graphs with minimum degree at least k and preconnected vertex deletions, using maxcut_strong_equilibrium_reduce_connected_core. It then splits into two cases based on whether G has a vertex of degree at least 2k. If such a vertex exists, the assumed hypothesis hbase directly supplies a strong equilibrium; otherwise, every vertex has degree at most 2k - 1, and the bounded-degree result maxcut_op89_exists_of_max_degree_le provides an optimal strong equilibrium.
It suffices to show the existence of a strong k-color equilibrium for finite graphs with preconnected vertex deletions and minimum degree at least k.
Applying the reduction theorem maxcut_strong_equilibrium_reduce_connected_core reduces the claim for all finite graphs to those whose single-vertex deletions are preconnected and where every vertex has degree at least k. We then fix an arbitrary finite graph G on vertex type V with these properties (named hpre and hmin).
uses
maxcut_strong_equilibrium_reduce_connected_coreapply maxcut_strong_equilibrium_reduce_connected_core intro V _ _ G _ hpre hmin
If G has a vertex of degree at least 2k, G has a strong k-color equilibrium.
We perform a case split on whether there exists a vertex v with degree at least 2k. In the positive branch, all preconditions of the hypothesis hbase (preconnected vertex deletions, minimum degree at least k, and maximum degree at least 2k) are satisfied, so hbase immediately yields the desired equilibrium.
by_cases hmax : ∃ v : V, 2 * k ≤ G.degree v · exact hbase V G hpre hmin hmax
In the negative branch, every vertex of G has degree at most 2k - 1.
Assuming no vertex has degree at least 2k, it follows that ¬(2k ≤ degree(v)) for each v. Linear arithmetic over ℕ (closed by omega) turns this into degree(v) ≤ 2k - 1.
· have hdeg : ∀ v : V, G.degree v ≤ 2 * k - 1 := by intro v have : ¬ (2 * k ≤ G.degree v) := fun h => hmax ⟨v, h⟩ omega
A strong k-color equilibrium exists for G when the maximum degree is at most 2k - 1.
Because k ≥ 3 and every vertex has degree at most 2k - 1, the lemma maxcut_op89_exists_of_max_degree_le guarantees the existence of a coloring σ that is an optimal strong equilibrium. Extracting σ and its strong equilibrium property completes the proof.
uses
maxcut_op89_exists_of_max_degree_lehave hopt := maxcut_op89_exists_of_max_degree_le G k hk hdeg rcases hopt with ⟨σ, _, hse⟩ exact ⟨σ, hse⟩
maxcut_strong_equilibrium_reduce_connected_core- For any natural number k, if every finite graph with preconnected single-vertex deletions and minimum degree at least k has a strong k-color equilibrium, then all finite graphs have a strong k-color equilibrium.
maxcut_op89_exists_of_max_degree_le- For k ≥ 3, any finite graph with maximum degree at most 2k - 1 has an optimal strong k-color equilibrium.
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_reduce_dense_core (k : ℕ) (hk : 3 ≤ k) (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], (∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected) → (∀ v : V, k ≤ G.degree v) → (∃ v : V, 2 * k ≤ G.degree v) → ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ) : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by apply maxcut_strong_equilibrium_reduce_connected_core intro V _ _ G _ hpre hmin by_cases hmax : ∃ v : V, 2 * k ≤ G.degree v · exact hbase V G hpre hmin hmax · have hdeg : ∀ v : V, G.degree v ≤ 2 * k - 1 := by intro v have : ¬ (2 * k ≤ G.degree v) := fun h => hmax ⟨v, h⟩ omega have hopt := maxcut_op89_exists_of_max_degree_le G k hk hdeg rcases hopt with ⟨σ, _, hse⟩ exact ⟨σ, hse⟩