maxcut_single_vertex_sum_strong_equilibrium_exists
For two induced subgraphs covering a finite graph, meeting in exactly one vertex, with no edges between their exclusive parts, strong equilibria on the two subgraphs imply a strong equilibrium on the whole graph.
Statement
theorem maxcut_single_vertex_sum_strong_equilibrium_exists {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (A B : Finset V) (o : V) (k : ℕ) (hcover : A ∪ B = Finset.univ) (hinter : A ∩ B = {o}) (hsep : ∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) (hA : ∃ σ : (↑A : Set V) → Fin k, is_maxcut_strong_equilibrium (G.induce (↑A : Set V)) σ) (hB : ∃ σ : (↑B : Set V) → Fin k, is_maxcut_strong_equilibrium (G.induce (↑B : Set V)) σ) : ∃ σ : 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 3
- maxcut_strong_equilibrium_color_permutationA global permutation of colors maps a strong equilibrium to a strong equilibrium.
- maxcut_single_vertex_sum_strong_equilibriumIf a finite graph is covered by two induced subgraphs meeting in one vertex with no edge between their exclusive parts, and a coloring…
- 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 2
- 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_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…
The proof, explained
To construct a strong equilibrium on the whole graph $G$, we start with strong equilibria $a$ on $G[A]$ and $b$ on $G[B]$. Because the strong equilibrium property is preserved under color permutations, we apply the transposition swapping $b(o)$ and $a(o)$ to obtain an equilibrium $b'$ on $G[B]$ that agrees with $a$ at the shared vertex $o$. We then glue $a$ and $b'$ into a global coloring $s : V → Fin k$. Finally, by the composition theorem for single-vertex graph sums (`maxcut_single_vertex_sum_strong_equilibrium`), $s$ is a strong equilibrium on $G$.
The cut vertex $o$ belongs to both $A$ and $B$.
Since the intersection $A \\cap B$ equals the singleton $\\{o\\}$ by the hypothesis hinter, and $o \\in \\{o\\}$ by `mem_singleton_self`, it follows that $o \\in A$ and $o \\in B$.
uses
mem_singleton_selfclassical have hoA : o ∈ A := (mem_inter.mp (by rw [hinter]; exact mem_singleton_self o)).1 have hoB : o ∈ B := (mem_inter.mp (by rw [hinter]; exact mem_singleton_self o)).2
There exist strong equilibria $a$ on $G[A]$ and $b$ on $G[B]$.
Unpacking the existential hypotheses hA and hB yields colorings $a : A \\to \\{0, \\dots, k-1\\}$ and $b : B \\to \\{0, \\dots, k-1\\}$ that are strong equilibria on the induced subgraphs $G[A]$ and $G[B]$, respectively.
obtain ⟨a, ha⟩ := hA obtain ⟨b, hb⟩ := hB
There exists a strong equilibrium $b'$ on $G[B]$ that agrees with $a$ at the shared vertex $o$.
Let $p$ be the transposition of colors swapping $b(o)$ and $a(o)$, and set $b' = p \\circ b$. By `maxcut_strong_equilibrium_color_permutation`, permuting the colors preserves the strong equilibrium property, so $b'$ is a strong equilibrium on $G[B]$. Furthermore, $p$ maps $b(o)$ to $a(o)$, so $b'(o) = a(o)$.
uses
maxcut_strong_equilibrium_color_permutationlet p : Equiv.Perm (Fin k) := Equiv.swap (b ⟨o, hoB⟩) (a ⟨o, hoA⟩) let b' := fun v => p (b v) have hb' : is_maxcut_strong_equilibrium (G.induce (↑B : Set V)) b' := maxcut_strong_equilibrium_color_permutation _ b p hb have hroot : b' ⟨o, hoB⟩ = a ⟨o, hoA⟩ := by simp [b', p]
A global coloring $s : V \\to \\{0, \\dots, k-1\\}$ is defined by gluing $a$ and $b'$.
For each vertex $v \\in V$, if $v \\in A$ we set $s(v) = a(v)$. Otherwise, since $A \\cup B = V$ (by `mem_univ` and the covering assumption hcover), $v$ must belong to $B$, so we set $s(v) = b'(v)$.
uses
mem_univlet s : V → Fin k := fun v => if h : v ∈ A then a ⟨v, h⟩ else b' ⟨v, by have : v ∈ A ∪ B := by rw [hcover]; exact mem_univ v exact (mem_union.mp this).resolve_left h⟩
The restriction of the glued coloring $s$ to $A$ coincides with $a$.
By function extensionality, for any vertex $v \\in A$, the definition of $s$ takes the positive branch $v \\in A$, so $s(v) = a(v)$.
have hsA : (fun v : (↑A : Set V) => s v.1) = a := by funext v simp [s, v.2]
The restriction of the glued coloring $s$ to $B$ coincides with $b'$.
For any vertex $v \\in B$, we split into two cases: if $v \\in A$, then $v \\in A \\cap B = \\{o\\}$, which forces $v = o$. At this vertex, $s(o) = a(o) = b'(o)$ by construction. If $v \\notin A$, the conditional in the definition of $s$ takes the negative branch, giving $s(v) = b'(v)$. Thus $s|_B = b'$.
have hsB : (fun v : (↑B : Set V) => s v.1) = b' := by funext v by_cases hv : v.1 ∈ A · have heq : v.1 = o := by have hm : v.1 ∈ A ∩ B := mem_inter.mpr ⟨hv, v.2⟩ rw [hinter] at hm exact mem_singleton.mp hm subst heq simpa [s, hoA] using hroot.symm · simp [s, hv]
The glued coloring $s$ is a strong equilibrium on the entire graph $G$.
By `maxcut_single_vertex_sum_strong_equilibrium`, when two induced subgraphs covering $G$ meet in a single vertex with no edges between their non-overlapping parts, any coloring whose restrictions to each subgraph are strong equilibria is a strong equilibrium on $G$. Since $s|_A = a$ and $s|_B = b'$ are strong equilibria, $s$ is a strong equilibrium on $G$.
uses
maxcut_single_vertex_sum_strong_equilibriumexact ⟨s, maxcut_single_vertex_sum_strong_equilibrium G A B o k s hcover hinter hsep (hsA ▸ ha) (hsB ▸ hb')⟩
mem_singleton_self- An element belongs to the singleton set containing only itself.
maxcut_strong_equilibrium_color_permutation- Permuting the color classes of a strong equilibrium in a Max-Cut game produces another strong equilibrium.
mem_univ- Every element of a finite type belongs to its universal finset.
maxcut_single_vertex_sum_strong_equilibrium- If a graph is covered by two induced subgraphs meeting in a single vertex with no edges between their exclusive parts, any coloring whose restrictions to both subgraphs are strong equilibria is a strong equilibrium on the whole graph.
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_single_vertex_sum_strong_equilibrium_exists {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (A B : Finset V) (o : V) (k : ℕ) (hcover : A ∪ B = Finset.univ) (hinter : A ∩ B = {o}) (hsep : ∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) (hA : ∃ σ : (↑A : Set V) → Fin k, is_maxcut_strong_equilibrium (G.induce (↑A : Set V)) σ) (hB : ∃ σ : (↑B : Set V) → Fin k, is_maxcut_strong_equilibrium (G.induce (↑B : Set V)) σ) : ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by classical have hoA : o ∈ A := (mem_inter.mp (by rw [hinter]; exact mem_singleton_self o)).1 have hoB : o ∈ B := (mem_inter.mp (by rw [hinter]; exact mem_singleton_self o)).2 obtain ⟨a, ha⟩ := hA obtain ⟨b, hb⟩ := hB let p : Equiv.Perm (Fin k) := Equiv.swap (b ⟨o, hoB⟩) (a ⟨o, hoA⟩) let b' := fun v => p (b v) have hb' : is_maxcut_strong_equilibrium (G.induce (↑B : Set V)) b' := maxcut_strong_equilibrium_color_permutation _ b p hb have hroot : b' ⟨o, hoB⟩ = a ⟨o, hoA⟩ := by simp [b', p] let s : V → Fin k := fun v => if h : v ∈ A then a ⟨v, h⟩ else b' ⟨v, by have : v ∈ A ∪ B := by rw [hcover]; exact mem_univ v exact (mem_union.mp this).resolve_left h⟩ have hsA : (fun v : (↑A : Set V) => s v.1) = a := by funext v simp [s, v.2] have hsB : (fun v : (↑B : Set V) => s v.1) = b' := by funext v by_cases hv : v.1 ∈ A · have heq : v.1 = o := by have hm : v.1 ∈ A ∩ B := mem_inter.mpr ⟨hv, v.2⟩ rw [hinter] at hm exact mem_singleton.mp hm subst heq simpa [s, hoA] using hroot.symm · simp [s, hv] exact ⟨s, maxcut_single_vertex_sum_strong_equilibrium G A B o k s hcover hinter hsep (hsA ▸ ha) (hsB ▸ hb')⟩