AFTD Auto-Formalizing Theoretical Domains

maxcut_single_vertex_sum_strong_equilibrium_exists

theoremverified

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
Used by 2

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$.

  1. 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$.

    lines 10–12

    uses mem_singleton_self

      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
  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.

    lines 13–14

      obtain ⟨a, ha⟩ := hA
      obtain ⟨b, hb⟩ := hB
  3. 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)$.

    lines 15–18

    uses maxcut_strong_equilibrium_color_permutation

      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]
  4. 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)$.

    lines 19–21

    uses mem_univ

      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⟩
  5. 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)$.

    lines 22–24

      have hsA : (fun v : (↑A : Set V) => s v.1) = a := by
        funext v
        simp [s, v.2]
  6. 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'$.

    lines 25–34

      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]
  7. 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$.

    line 35

    uses maxcut_single_vertex_sum_strong_equilibrium

      exact ⟨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

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')⟩
See it in the graphDiscuss this resultChallenge it