maxcut_strong_equilibrium_reduce_vertex_deletions
Fix k. If every finite graph whose every vertex deletion is preconnected has a strong k-color equilibrium, then every finite graph has a strong k-color equilibrium.
Statement
theorem maxcut_strong_equilibrium_reduce_vertex_deletions (k : ℕ) (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], (∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected) → ∃ σ : 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 problem in arXiv:2610.04948, Section 4.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- maxcut_strong_equilibrium_reduce_single_vertex_sumsFor any fixed number of colors, if every finite graph with decidable equality and adjacency that has no nontrivial separation into two…
- maxcut_one_sum_indecomposable_delete_preconnectedIf a finite graph has no nontrivial separation into two induced pieces meeting at one vertex, then after deleting any vertex every two…
- 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 for general finite graphs to graphs whose single-vertex deletions are preconnected. First, `maxcut_strong_equilibrium_reduce_single_vertex_sums` reduces the problem to graphs that are indecomposable under 1-sums (clique-sums over a single vertex). Second, `maxcut_one_sum_indecomposable_delete_preconnected` shows that deleting any vertex from such a 1-sum indecomposable graph leaves a preconnected subgraph. Finally, the assumption `hbase` directly supplies the required strong equilibrium.
It suffices to prove the existence of a strong k-color equilibrium for graphs that are indecomposable under 1-sums.
By `maxcut_strong_equilibrium_reduce_single_vertex_sums`, the theorem reduces to showing that an equilibrium exists for every graph G that cannot be non-trivially split into two subgraphs A and B meeting at a single vertex o with no edges connecting A \ {o} and B \ {o}.
uses
maxcut_strong_equilibrium_reduce_single_vertex_sumsapply maxcut_strong_equilibrium_reduce_single_vertex_sums kEvery finite 1-sum indecomposable graph has a strong k-color equilibrium.
Let G be a finite graph satisfying the 1-sum indecomposability condition (hind). By `maxcut_one_sum_indecomposable_delete_preconnected`, deleting any vertex o from G leaves a preconnected induced subgraph. This satisfies the precondition of the hypothesis hbase, which then directly provides a strong k-color equilibrium for G.
uses
maxcut_one_sum_indecomposable_delete_preconnectedintro V _ _ G _ hind exact hbase V G (maxcut_one_sum_indecomposable_delete_preconnected G hind)
maxcut_strong_equilibrium_reduce_single_vertex_sums- If every finite graph that cannot be decomposed into two subgraphs meeting at a single vertex with no edges between them admits a strong k-color equilibrium, then every finite graph admits a strong k-color equilibrium.
maxcut_one_sum_indecomposable_delete_preconnected- In a finite graph that cannot be non-trivially decomposed into two subgraphs intersecting at a single vertex with no edges between them, deleting any single vertex leaves a preconnected induced subgraph.
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.
open Finsettheorem maxcut_strong_equilibrium_reduce_vertex_deletions (k : ℕ) (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], (∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected) → ∃ σ : 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_single_vertex_sums k intro V _ _ G _ hind exact hbase V G (maxcut_one_sum_indecomposable_delete_preconnected G hind)