maxcut_strong_equilibrium_reduce_connected_core
Fix k. If every finite graph of minimum degree at least k 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_connected_core (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 → 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 4
- maxcut_strong_equilibrium_extend_low_degree_vertexIf a vertex has degree strictly smaller than the number k of available colors, a strong equilibrium of the induced graph obtained by…
- maxcut_single_vertex_sum_strong_equilibrium_existsFor two induced subgraphs covering a finite graph, meeting in exactly one vertex, with no edges between their exclusive parts, strong…
- 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.
- Used by 1
- maxcut_strong_equilibrium_reduce_dense_coreFix k at least three. If every finite graph of minimum degree at least k, with preconnected vertex deletions and with some vertex of…
The proof, explained
The theorem is proved by strong induction on the number of vertices |V| of a finite graph G. If G has a vertex v with degree less than k, removing v yields a strictly smaller graph that has an equilibrium by induction, which extends to v. If G decomposes into a non-trivial 1-sum of two subgraphs sharing a single vertex, the induction hypothesis provides equilibria on both pieces that can be glued together. Otherwise, G has minimum degree at least k and is 1-sum indecomposable (meaning every single-vertex deletion is preconnected), so the result follows directly from the assumed base hypothesis.
It suffices to prove by strong induction on n that every finite graph G with |V| ≤ n has a strong k-color equilibrium.
We activate classical logic and state the inductive assertion h for graphs of size bounded by n. Using strong induction on n (via Nat.strong_induction_on), we assume as induction hypothesis (ih) that every graph with strictly fewer than n vertices has a strong k-color equilibrium, and then introduce an arbitrary graph G with |V| ≤ n.
uses
Nat.strong_induction_onclassical have h : ∀ n : ℕ, ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], Fintype.card V ≤ n → ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by intro n induction n using Nat.strong_induction_on with | h n ih => intro V _ _ G _ hn
If G has a vertex of degree strictly less than k, then G has a strong k-color equilibrium.
Suppose there is a vertex v with deg(v) < k. We remove v to form the induced subgraph on A = V \ {v}. Since v ∉ A, A is a proper subset of V, so |A| < |V| ≤ n. By the induction hypothesis, G[A] admits a strong k-color equilibrium. Because deg(v) < k, maxcut_strong_equilibrium_extend_low_degree_vertex extends this coloring to v, yielding a strong k-color equilibrium on G.
uses
mem_univ,lt_of_lt_of_le,Finset.card_lt_card,Finset.ssubset_iff_subset_ne.mpr,Finset.subset_univ,le_refl,maxcut_strong_equilibrium_extend_low_degree_vertexby_cases hlow : ∃ v : V, G.degree v < k · obtain ⟨v, hv⟩ := hlow let A : Finset V := Finset.univ.erase v have hne : A ≠ Finset.univ := by intro he have hvA : v ∈ A := by rw [he]; exact mem_univ v simpa [A] using hvA have hcard : Fintype.card (↑A : Set V) < n := by apply lt_of_lt_of_le _ hn simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ A, hne⟩) have hex := ih _ hcard (↑A : Set V) (G.induce (↑A : Set V)) (le_refl _) exact maxcut_strong_equilibrium_extend_low_degree_vertex G v k hv hex
If G decomposes as a non-trivial 1-sum over a cut vertex, then G has a strong k-color equilibrium.
Suppose V splits into two proper subgraphs A, B ⊊ V that overlap only at a single vertex o (A ∩ B = {o}) with no edges between A \ {o} and B \ {o}. Because A and B are proper subsets of V, their sizes are strictly less than n. The induction hypothesis provides strong k-color equilibria on both G[A] and G[B]. By maxcut_single_vertex_sum_strong_equilibrium_exists, these two equilibria can be glued at o to form a strong k-color equilibrium on G.
uses
lt_of_lt_of_le,Finset.card_lt_card,Finset.ssubset_iff_subset_ne.mpr,Finset.subset_univ,le_refl,maxcut_single_vertex_sum_strong_equilibrium_exists· by_cases hs : ∃ (A B : Finset V) (o : V), A ∪ B = Finset.univ ∧ A ∩ B = {o} ∧ (∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) ∧ A ≠ Finset.univ ∧ B ≠ Finset.univ · obtain ⟨A, B, o, hcover, hinter, hsep, hA, hB⟩ := hs have hcardA : Fintype.card (↑A : Set V) < n := by apply lt_of_lt_of_le _ hn simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ A, hA⟩) have hcardB : Fintype.card (↑B : Set V) < n := by apply lt_of_lt_of_le _ hn simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ B, hB⟩) have ea := ih _ hcardA (↑A : Set V) (G.induce (↑A : Set V)) (le_refl _) have eb := ih _ hcardB (↑B : Set V) (G.induce (↑B : Set V)) (le_refl _) exact maxcut_single_vertex_sum_strong_equilibrium_exists G A B o k hcover hinter hsep ea eb
If neither reduction applies, G satisfies the base hypothesis and therefore has a strong k-color equilibrium.
When there are no vertices of degree less than k and no 1-sum decompositions, the minimum degree of G is at least k. Furthermore, by maxcut_one_sum_indecomposable_delete_preconnected, 1-sum indecomposability implies that deleting any vertex o leaves a preconnected induced subgraph. Hence G meets all premises of the base assumption hbase, which supplies the strong k-color equilibrium.
uses
maxcut_one_sum_indecomposable_delete_preconnected· apply hbase V G · apply maxcut_one_sum_indecomposable_delete_preconnected G intro A B o hc hi hsep by_contra hbad push Not at hbad exact hs ⟨A, B, o, hc, hi, hsep, hbad.1, hbad.2⟩ · intro v by_contra hn exact hlow ⟨v, by omega⟩
Every finite graph has a strong k-color equilibrium.
Given any finite graph G on vertex set V, we apply the general result h with n = |V| and the trivial inequality |V| ≤ |V|, concluding the theorem.
uses
le_reflintro V _ _ G _ exact h (Fintype.card V) V G (le_refl _)
Nat.strong_induction_on- The principle of strong induction on natural numbers: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) holds for all m < n.
mem_univ- Every element of a finite type belongs to its universal finset.
lt_of_lt_of_le- Transitivity of strict and non-strict inequality: if a < b and b ≤ c, then a < c.
Finset.card_lt_card- A proper subset of a finite set has strictly smaller cardinality.
Finset.ssubset_iff_subset_ne.mpr- If a subset is not equal to the whole set, it is a proper (strict) subset.
Finset.subset_univ- Every finset in a finite type is a subset of the universal finset.
le_refl- Reflexivity of inequality: a ≤ a for all a.
maxcut_strong_equilibrium_extend_low_degree_vertex- If a vertex v has degree strictly less than k, any strong k-color equilibrium on G \ {v} extends to a strong k-color equilibrium on G.
maxcut_single_vertex_sum_strong_equilibrium_exists- If a graph is a 1-sum of two induced subgraphs A and B meeting at a single vertex o, strong k-color equilibria on G[A] and G[B] combine into a strong k-color equilibrium on G.
maxcut_one_sum_indecomposable_delete_preconnected- If a graph cannot be non-trivially decomposed as a 1-sum at any vertex, then deleting any single vertex yields a preconnected subgraph.
- Strong induction is formalized using an explicit natural number upper bound n on the cardinality |V| ≤ n, which is specialized to n = |V| at the conclusion of the proof.
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_connected_core (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 → 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 classical have h : ∀ n : ℕ, ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], Fintype.card V ≤ n → ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by intro n induction n using Nat.strong_induction_on with | h n ih => intro V _ _ G _ hn by_cases hlow : ∃ v : V, G.degree v < k · obtain ⟨v, hv⟩ := hlow let A : Finset V := Finset.univ.erase v have hne : A ≠ Finset.univ := by intro he have hvA : v ∈ A := by rw [he]; exact mem_univ v simpa [A] using hvA have hcard : Fintype.card (↑A : Set V) < n := by apply lt_of_lt_of_le _ hn simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ A, hne⟩) have hex := ih _ hcard (↑A : Set V) (G.induce (↑A : Set V)) (le_refl _) exact maxcut_strong_equilibrium_extend_low_degree_vertex G v k hv hex · by_cases hs : ∃ (A B : Finset V) (o : V), A ∪ B = Finset.univ ∧ A ∩ B = {o} ∧ (∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) ∧ A ≠ Finset.univ ∧ B ≠ Finset.univ · obtain ⟨A, B, o, hcover, hinter, hsep, hA, hB⟩ := hs have hcardA : Fintype.card (↑A : Set V) < n := by apply lt_of_lt_of_le _ hn simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ A, hA⟩) have hcardB : Fintype.card (↑B : Set V) < n := by apply lt_of_lt_of_le _ hn simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ B, hB⟩) have ea := ih _ hcardA (↑A : Set V) (G.induce (↑A : Set V)) (le_refl _) have eb := ih _ hcardB (↑B : Set V) (G.induce (↑B : Set V)) (le_refl _) exact maxcut_single_vertex_sum_strong_equilibrium_exists G A B o k hcover hinter hsep ea eb · apply hbase V G · apply maxcut_one_sum_indecomposable_delete_preconnected G intro A B o hc hi hsep by_contra hbad push Not at hbad exact hs ⟨A, B, o, hc, hi, hsep, hbad.1, hbad.2⟩ · intro v by_contra hn exact hlow ⟨v, by omega⟩ intro V _ _ G _ exact h (Fintype.card V) V G (le_refl _)