maxcut_strong_equilibrium_reduce_single_vertex_sums
For any fixed number of colors, if every finite graph with decidable equality and adjacency that has no nontrivial separation into two induced pieces meeting at one vertex has a strong equilibrium, then every finite graph with decidable equality and adjacency has a strong equilibrium. A separation is nontrivial when neither piece contains all vertices and there are no edges between the exclusive parts.
Statement
theorem maxcut_strong_equilibrium_reduce_single_vertex_sums (k : ℕ) (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], (∀ (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) → ∃ σ : 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 strong-equilibrium existence problem; the two-piece gluing step is maxcut_single_vertex_sum_strong_equilibrium.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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_vertex_deletionsFix k. If every finite graph whose every vertex deletion is preconnected has a strong k-color equilibrium, then every finite graph has a…
The proof, explained
The proof proceeds by strong induction on the number of vertices n of the graph. If the graph admits a nontrivial single-vertex separation into two proper pieces with no edges between their disjoint parts, both pieces have strictly fewer vertices, so by the induction hypothesis each admits a strong equilibrium; these are then glued together into a strong equilibrium for the whole graph. Otherwise, the graph has no nontrivial single-vertex separation, so the base hypothesis immediately yields a strong equilibrium.
To prove the theorem, it suffices to prove by strong induction on n that every graph on at most n vertices has a strong equilibrium.
We introduce an auxiliary property h stating that every finite graph G with |V| ≤ n has a strong k-color max-cut equilibrium. We proceed by strong induction on n using Nat.strong_induction_on, which provides the induction hypothesis ih that the property holds for all m < n. We then consider a graph G on a vertex type V satisfying |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
The inductive step reduces to two cases: either G admits a nontrivial single-vertex separation, or it does not.
We split into cases (using by_cases) on the existence of subsets A, B ⊆ V and a vertex o ∈ V covering V and intersecting only at o, with no edges between A \\ B and B \\ A, such that neither A nor B is all of V.
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.univIf G admits a nontrivial single-vertex separation, then G has a strong equilibrium.
Given the separation into A and B meeting at o, since A ≠ V and B ≠ V, both A and B are strict subsets of V and therefore have strictly fewer than |V| ≤ n vertices by Finset.card_lt_card, Finset.ssubset_iff_subset_ne.mpr, Finset.subset_univ, and lt_of_lt_of_le. Applying the induction hypothesis ih to the induced subgraphs on A and B yields strong equilibria ea and eb on each piece. Finally, maxcut_single_vertex_sum_strong_equilibrium_exists combines these two equilibria into a strong 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· 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 G admits no nontrivial single-vertex separation, then G has a strong equilibrium.
When G has no nontrivial single-vertex separation, it satisfies the premise of the base hypothesis hbase. Indeed, if there were any single-vertex separation with A ≠ V and B ≠ V, this would contradict the negation of hs. Thus hbase directly supplies a strong equilibrium for G.
· apply hbase V G intro A B o hc hi hn by_contra hbad push Not at hbad exact hs ⟨A, B, o, hc, hi, hn, hbad.1, hbad.2⟩
Every finite graph has a strong equilibrium.
Given an arbitrary finite graph G on vertex set V, we apply the auxiliary inductive result h with n = |V| and the trivial bound |V| ≤ |V| provided by le_refl.
uses
le_reflintro V _ _ G _ exact h (Fintype.card V) V G (le_refl _)
Nat.strong_induction_on- The principle of strong induction on ℕ: to prove P(n) for all n, it suffices to prove P(n) under the assumption that P(m) holds for all m < n.
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 strictly smaller finite set has strictly smaller cardinality: if s ⊂ t, then |s| < |t|.
Finset.ssubset_iff_subset_ne.mpr- If s ⊆ t and s ≠ t, then s is a strict subset of t (s ⊂ t).
Finset.subset_univ- Every finset of elements from a finite type is a subset of the universal finset.
le_refl- Reflexivity of the partial order ≤: for any a, a ≤ a.
maxcut_single_vertex_sum_strong_equilibrium_exists- If a graph is decomposed into two induced subgraphs on vertex subsets A and B that cover all vertices, intersect at a single vertex, and have no edges between A \\ B and B \\ A, and if both induced subgraphs admit a strong max-cut equilibrium, then the whole graph admits a strong max-cut equilibrium.
- In proving $|A| < n$ and $|B| < n$ (lines 24 and 27), the proof uses `simpa` to bridge between the cardinality of a finset and the `Fintype` cardinality of its coerced subtype.
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_single_vertex_sums (k : ℕ) (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], (∀ (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) → ∃ σ : 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 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 intro A B o hc hi hn by_contra hbad push Not at hbad exact hs ⟨A, B, o, hc, hi, hn, hbad.1, hbad.2⟩ intro V _ _ G _ exact h (Fintype.card V) V G (le_refl _)