AFTD Auto-Formalizing Theoretical Domains

maxcut_single_vertex_sum_strong_equilibrium

theoremverified

If a finite graph is covered by two induced subgraphs meeting in one vertex with no edge between their exclusive parts, and a coloring restricts to a strong equilibrium on each induced subgraph, then the coloring is a strong equilibrium on the entire graph.

Statement

theorem maxcut_single_vertex_sum_strong_equilibrium
    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (A B : Finset V) (o : V) (k : ℕ) (σ : V → Fin k)
    (hcover : A ∪ B = Finset.univ) (hinter : A ∩ B = {o})
    (hsep : ∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w)
    (hA : is_maxcut_strong_equilibrium (G.induce (↑A : Set V)) (fun v => σ v.1))
    (hB : is_maxcut_strong_equilibrium (G.induce (↑B : Set V)) (fun v => σ v.1)) :
    is_maxcut_strong_equilibrium G σ
Source
Structural reduction for OP-85, the general strong-equilibrium existence question; supported on five-vertex decompositions by experiment 12429.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_single_vertex_gluing_abstractFor an additively separable game whose player sets cover all players and intersect only at a shared player, stability on each piece…
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
  • is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
  • maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
Used by 2

The proof, explained

The proof decomposes the utility of any vertex in G = A ∪ B into the sum of its payoffs in the two induced subgraphs G[A] and G[B], which is valid because their intersection is a single vertex with no self-loops and there are no edges between A \\ B and B \\ A. Because σ is a strong equilibrium on each induced subgraph, any deviation affecting A or B must leave at least one deviating vertex without a payoff increase in that subgraph. An abstract single-vertex gluing lemma combines these local non-improvement conditions to find a deviating vertex whose total utility cannot strictly increase, ruling out any profitable strong deviation on G.

  1. The cardinality of the subtype of A satisfying predicate P equals the cardinality of the finset A filtered by P.

    We construct a bijection between the subtype of elements of A satisfying P and the filtered finset of elements in A satisfying P via the subtype projection w ↦ w.1. Injectivity follows from subtype extensionality (`Subtype.ext`), and surjectivity holds because any b ∈ A satisfying P(b) is the projection of the subtype pair ⟨b, hb.1⟩.

    lines 14–24

    uses Finset.card_bij, mem_filter, mem_univ, true_and, Subtype.ext

      apply Finset.card_bij (fun (w : (↑A : Set V)) _ => w.1)
      · intro w hw
        simp only [mem_filter, mem_univ, true_and] at hw
        simp only [mem_filter]
        exact ⟨w.2, hw⟩
      · intro w1 _ w2 _ h
        exact Subtype.ext h
      · intro b hb
        simp only [mem_filter] at hb
        use ⟨b, hb.1⟩
        simp [hb.2]
  2. For v ∈ A, the restricted payoff in A equals the number of neighbors in A having a different color.

    Unfolding the definition of payoff in A, the hypothesis v ∈ A selects the positive branch of the definition (`dif_pos`). The utility in the induced subgraph on A counts elements of the subtype satisfying the condition; applying the subtype cardinality lemma rewrites this count as the cardinality of the filtered finset of neighbors in A with different colors.

    lines 31–33

    uses dif_pos, maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype

      dsimp [maxcut_single_vertex_sum_strong_equilibrium_a_payoff]
      rw [dif_pos hv]
      exact maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype A (fun w => G.Adj v w ∧ p w ≠ p v)
  3. When v ∈ A ∩ B (so v = o), the total utility of v in G equals the sum of its restricted payoffs in A and in B.

    Because A ∩ B = {o}, having v ∈ A and v ∈ B forces v = o. Since A ∪ B = V, the neighbors of v with different colors are partitioned into those in A and those in B. Their intersection is contained in A ∩ B = {o}, but o cannot be a neighbor of itself because simple graphs are loopless (`G.irrefl`), so the intersection is empty. Disjointness allows the cardinality of the union to be split into the sum of the payoffs in A and B.

    lines 43–63

    uses mem_inter.mpr, mem_singleton.mp, maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq, filter_union, disjoint_iff_inter_eq_empty, filter_inter_distrib, filter_singleton, False.elim, card_union_of_disjoint

      let P := fun w => G.Adj v w ∧ p w ≠ p v
      have hP_univ : maxcut_utility G p v = (Finset.univ.filter P).card := rfl
      by_cases hvA : v ∈ A
      · by_cases hvB : v ∈ B
        · have hvo : v = o := by
            have : v ∈ A ∩ B := mem_inter.mpr ⟨hvA, hvB⟩
            rw [hinter] at this
            exact mem_singleton.mp this
          rw [maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq G A p v hvA,
              maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq G B p v hvB]
          rw [hP_univ]
          have hunion : Finset.univ.filter P = (A.filter P) ∪ (B.filter P) := by
            rw [← filter_union, hcover]
          have hdisj : Disjoint (A.filter P) (B.filter P) := by
            rw [disjoint_iff_inter_eq_empty, ← filter_inter_distrib, hinter]
            rw [filter_singleton]
            split_ifs with hPo
            · subst hvo
              exact False.elim (G.irrefl hPo.1)
            · rfl
          rw [hunion, card_union_of_disjoint hdisj]
  4. When v ∈ A \\ B, the restricted payoff in B is zero and the total utility in G equals the restricted payoff in A.

    Since v ∉ B, the payoff in B is zero by definition (`dif_neg`). To show that the total utility equals the payoff in A, we observe that every neighbor w of v in G must lie in A: if w were not in A, then since A ∪ B = V it would lie in B \\ A, directly contradicting the separation assumption that there are no edges between A \\ B and B \\ A.

    lines 64–79

    uses dif_neg, add_zero, maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq, mem_filter, mem_univ, true_and, mem_union.mp

        · have hpayB : maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B p v = 0 := dif_neg hvB
          rw [hP_univ, hpayB, add_zero, maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq G A p v hvA]
          congr 1
          ext w
          simp only [mem_filter, mem_univ, true_and]
          constructor
          · intro hw
            have hwA : w ∈ A := by
              by_contra hnwA
              have hwB : w ∈ B := by
                have : w ∈ A ∪ B := by rw [hcover]; exact mem_univ w
                exact (mem_union.mp this).resolve_left hnwA
              exact hsep v hvA hvB w hwB hnwA hw.1
            exact ⟨hwA, hw⟩
          · intro hw
            exact hw.2
  5. When v ∉ A (so v ∈ B \\ A), the restricted payoff in A is zero and the total utility in G equals the restricted payoff in B.

    Since A ∪ B = V, v ∉ A implies v ∈ B. Symmetrically to the previous case, the payoff in A is zero (`dif_neg`). By edge symmetry and the separation hypothesis, any neighbor of v must lie in B, so the total utility in G equals the payoff in B.

    lines 80–99

    uses mem_univ, mem_union.mp, dif_neg, zero_add, maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq, mem_filter, true_and

      · have hvB : v ∈ B := by
          have : v ∈ A ∪ B := by rw [hcover]; exact mem_univ v
          exact (mem_union.mp this).resolve_left hvA
        have hpayA : maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A p v = 0 := dif_neg hvA
        rw [hP_univ, hpayA, zero_add, maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq G B p v hvB]
        congr 1
        ext w
        simp only [mem_filter, mem_univ, true_and]
        constructor
        · intro hw
          have hwB : w ∈ B := by
            by_contra hnwB
            have hwA : w ∈ A := by
              have : w ∈ A ∪ B := by rw [hcover]; exact mem_univ w
              exact (mem_union.mp this).resolve_right hnwB
            have : ¬ G.Adj w v := hsep w hwA hnwB v hvB hvA
            exact this (G.adj_symm hw.1)
          exact ⟨hwB, hw⟩
        · intro hw
          exact hw.2
  6. If σ is a strong equilibrium on G[A], then any coloring τ that differs from σ somewhere on A has a deviating vertex in A whose restricted payoff does not increase.

    We proceed by contradiction: if every deviating vertex in A strictly increased its payoff in A, the set SA of deviating vertices in A would form a non-empty coalition where all members strictly gain utility in G[A] and no vertex outside SA changes color. This would constitute a successful strong deviation in G[A], contradicting the assumption that σ restricts to a strong equilibrium on G[A].

    lines 109–148

    uses mem_filter, mem_univ, False.elim

      by_contra hnot
      have hnot' : ∀ v ∈ (↑A : Set V), τ v ≠ σ v →
          maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A σ v <
          maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A τ v := by
        intro v hv hd
        by_contra hle
        push Not at hle
        exact hnot ⟨v, hv, hd, hle⟩
      obtain ⟨v0, hv0A, hd0⟩ := hchanged
      let GA := G.induce (↑A : Set V)
      let σA : (↑A : Set V) → Fin k := fun v => σ v.1
      let τA : (↑A : Set V) → Fin k := fun v => τ v.1
      let SA : Finset (↑A : Set V) := Finset.univ.filter (fun v => τA v ≠ σA v)
      have hdev : is_maxcut_strong_deviation GA σA SA τA := by
        refine ⟨?_, ?_, ?_⟩
        · refine ⟨⟨v0, hv0A⟩, ?_⟩
          rw [mem_filter]
          exact ⟨mem_univ _, hd0⟩
        · intro v hv
          rw [mem_filter] at hv
          push Not at hv
          exact hv (mem_univ v)
        · intro v hv
          rw [mem_filter] at hv
          have hne : τ v.1 ≠ σ v.1 := hv.2
          have hvA : v.1 ∈ (↑A : Set V) := v.2
          have hlt := hnot' v.1 hvA hne
          have ha_σ : maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A σ v.1 = maxcut_utility GA σA v := by
            dsimp [maxcut_single_vertex_sum_strong_equilibrium_a_payoff]
            split_ifs with h
            · rfl
            · exact False.elim (h v.2)
          have ha_τ : maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A τ v.1 = maxcut_utility GA τA v := by
            dsimp [maxcut_single_vertex_sum_strong_equilibrium_a_payoff]
            split_ifs with h
            · rfl
            · exact False.elim (h v.2)
          rw [ha_σ, ha_τ] at hlt
          exact hlt
      exact hA SA τA hdev
  7. The hypotheses of the abstract gluing theorem are satisfied for the decomposed payoffs on A and B.

    We verify the requirements of `maxcut_single_vertex_gluing_abstract`: the intersection vertex o belongs to both A and B; A and B cover the vertex set; their intersection is {o}; payoffs outside A and B vanish; and deviations changing vertices in A or B have non-improving deviators by the stability lemma. Applying the gluing theorem yields that any coloring differing from σ has a deviator whose combined payoff in A and B does not increase.

    lines 158–193

    uses mem_singleton_self, mem_inter.mp, mem_univ, mem_union.mp, mem_inter.mpr, mem_singleton.mp, dif_neg, maxcut_single_vertex_sum_strong_equilibrium_hstable_of_eq, maxcut_single_vertex_gluing_abstract

      have hoA : o ∈ (↑A : Set V) := by
        have : o ∈ A ∩ B := by rw [hinter]; exact mem_singleton_self o
        exact (mem_inter.mp this).1
      have hoB : o ∈ (↑B : Set V) := by
        have : o ∈ A ∩ B := by rw [hinter]; exact mem_singleton_self o
        exact (mem_inter.mp this).2
      have hcov : ∀ v, v ∈ (↑A : Set V) ∨ v ∈ (↑B : Set V) := by
        intro v
        have : v ∈ A ∪ B := by rw [hcover]; exact mem_univ v
        exact mem_union.mp this
      have hint : ∀ v, v ∈ (↑A : Set V) → v ∈ (↑B : Set V) → v = o := by
        intro v hvA hvB
        have : v ∈ A ∩ B := mem_inter.mpr ⟨hvA, hvB⟩
        rw [hinter] at this
        exact mem_singleton.mp this
      have ha0 : ∀ (p : V → Fin k) (v : V), v ∉ (↑A : Set V) →
          maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A p v = 0 :=
        fun p v hv => dif_neg hv
      have hb0 : ∀ (p : V → Fin k) (v : V), v ∉ (↑B : Set V) →
          maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B p v = 0 :=
        fun p v hv => dif_neg hv
      have hstabA : ∀ τ, (∃ v, v ∈ (↑A : Set V) ∧ τ v ≠ σ v) →
          ∃ v, v ∈ (↑A : Set V) ∧ τ v ≠ σ v ∧
            maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A τ v ≤
            maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A σ v :=
        fun τ h => maxcut_single_vertex_sum_strong_equilibrium_hstable_of_eq G A k σ hA τ h
      have hstabB : ∀ τ, (∃ v, v ∈ (↑B : Set V) ∧ τ v ≠ σ v) →
          ∃ v, v ∈ (↑B : Set V) ∧ τ v ≠ σ v ∧
            maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B τ v ≤
            maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B σ v :=
        fun τ h => maxcut_single_vertex_sum_strong_equilibrium_hstable_of_eq G B k σ hB τ h
      have hglue := maxcut_single_vertex_gluing_abstract σ (↑A : Set V) (↑B : Set V) o
        hoA hoB hcov hint
        (maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A)
        (maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B)
        ha0 hb0 hstabA hstabB
  8. Any strong deviation coalition S must produce a coloring τ that differs from σ at some vertex.

    If τ agreed with σ everywhere on V, then every vertex v0 in S (which is non-empty) would have identical utilities under τ and σ. This contradicts the definition of a strong deviation, which requires utility to strictly increase for all vertices in S.

    lines 194–208

    uses mem_filter, mem_univ, true_and, Nat.lt_irrefl

      intro S τ hdev
      rcases hdev with ⟨hne, houtside, hgain⟩
      have hdiff : ∃ v, τ v ≠ σ v := by
        by_contra hsame
        push Not at hsame
        obtain ⟨v0, hv0⟩ := hne
        have hg := hgain v0 hv0
        have hu_eq : maxcut_utility G τ v0 = maxcut_utility G σ v0 := by
          dsimp [maxcut_utility]
          congr 1
          ext w
          simp only [mem_filter, mem_univ, true_and]
          rw [hsame w, hsame v0]
        rw [hu_eq] at hg
        exact Nat.lt_irrefl _ hg
  9. No strong deviation exists on G, so σ is a strong equilibrium on the entire graph.

    By the gluing result, the non-trivial deviation τ has a deviating vertex v whose combined payoff does not increase: a(τ, v) + b(τ, v) ≤ a(σ, v) + b(σ, v). Because τ agrees with σ outside S, v must belong to S. By definition of a strong deviation, v must strictly gain utility: utility(G, σ, v) < utility(G, τ, v). Rewriting utility as the sum of payoffs in A and B via the utility decomposition lemma yields a(σ, v) + b(σ, v) < a(τ, v) + b(τ, v), directly contradicting the weak inequality.

    lines 209–216

    uses maxcut_single_vertex_sum_strong_equilibrium_utility_eq_sum_payoffs, Nat.not_le_of_lt

      obtain ⟨v, hvd, hle⟩ := hglue τ hdiff
      have hvS : v ∈ S := by
        by_contra hnvS
        exact hvd (houtside v hnvS)
      have hg := hgain v hvS
      rw [maxcut_single_vertex_sum_strong_equilibrium_utility_eq_sum_payoffs G A B o k τ hcover hinter hsep v,
          maxcut_single_vertex_sum_strong_equilibrium_utility_eq_sum_payoffs G A B o k σ hcover hinter hsep v] at hg
      exact Nat.not_le_of_lt hg hle
Finset.card_bij
Two finite sets have the same cardinality if there exists a bijection between them.
mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
mem_univ
Every element of a finite type belongs to its universal set.
true_and
Conjunction with True simplifies to the proposition itself.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
dif_pos
A dependent if-then-else evaluates to its positive branch when the condition holds.
maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype
For a finset A and predicate P, the cardinality of the subtype of A satisfying P equals the cardinality of A filtered by P.
mem_inter.mpr
If an element belongs to both sets, it belongs to their intersection.
mem_singleton.mp
If an element belongs to a singleton set {a}, it equals a.
maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq
For v in A, the payoff of v restricted to A equals the number of neighbors of v in A with a different color.
filter_union
Filtering distributes over union of finsets.
disjoint_iff_inter_eq_empty
Two finsets are disjoint if and only if their intersection is empty.
filter_inter_distrib
Filtering distributes over intersection of finsets.
filter_singleton
Filtering a singleton set yields the singleton if the element satisfies the predicate, and empty otherwise.
False.elim
From a contradiction (False), any conclusion follows.
card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
dif_neg
A dependent if-then-else evaluates to its negative branch when the condition is false.
add_zero
Adding zero on the right leaves the value unchanged.
mem_union.mp
If an element belongs to a union of sets, it belongs to the first set or the second set.
zero_add
Adding zero on the left leaves the value unchanged.
mem_singleton_self
Every element belongs to its own singleton set.
mem_inter.mp
If an element belongs to the intersection of two sets, it belongs to each set.
maxcut_single_vertex_sum_strong_equilibrium_hstable_of_eq
In a graph where a coloring restricts to a strong equilibrium on an induced subgraph A, any deviation changing vertices in A has at least one deviating vertex in A whose payoff in A does not increase.
maxcut_single_vertex_gluing_abstract
Abstract gluing theorem: if two subgraphs meet at a single vertex with separated interiors and each satisfies deviation stability, any global deviation has a vertex whose combined payoff does not increase.
Nat.lt_irrefl
Strict inequality on natural numbers is irreflexive (no number is strictly less than itself).
maxcut_single_vertex_sum_strong_equilibrium_utility_eq_sum_payoffs
In a graph covered by A and B meeting at a single vertex with no edges between A \\ B and B \\ A, the total utility of any vertex equals the sum of its payoffs in A and B.
Nat.not_le_of_lt
If a < b for natural numbers, then b is not less than or equal to a.

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 Finsetdef maxcut_single_vertex_sum_strong_equilibrium_a_payoff    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (A : Finset V) {k : ℕ} (p : V → Fin k) (v : V) : ℕ :=  if hv : v ∈ A then    maxcut_utility (G.induce (↑A : Set V)) (fun (w : (↑A : Set V)) => p w.1) ⟨v, hv⟩  else 0theorem maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype    {V : Type} [Fintype V] [DecidableEq V]    (A : Finset V) (P : V → Prop) [DecidablePred P] :  (Finset.univ.filter (fun (w : (↑A : Set V)) => P w.1)).card = (A.filter P).card := by  apply Finset.card_bij (fun (w : (↑A : Set V)) _ => w.1)  · intro w hw    simp only [mem_filter, mem_univ, true_and] at hw    simp only [mem_filter]    exact ⟨w.2, hw⟩  · intro w1 _ w2 _ h    exact Subtype.ext h  · intro b hb    simp only [mem_filter] at hb    use ⟨b, hb.1⟩    simp [hb.2]lemma maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (A : Finset V) {k : ℕ} (p : V → Fin k) (v : V) (hv : v ∈ A) :    maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A p v =      (A.filter (fun w => G.Adj v w ∧ p w ≠ p v)).card := by  dsimp [maxcut_single_vertex_sum_strong_equilibrium_a_payoff]  rw [dif_pos hv]  exact maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype A (fun w => G.Adj v w ∧ p w ≠ p v)lemma maxcut_single_vertex_sum_strong_equilibrium_utility_eq_sum_payoffs    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (A B : Finset V) (o : V) (k : ℕ) (p : V → Fin k)    (hcover : A ∪ B = Finset.univ) (hinter : A ∩ B = {o})    (hsep : ∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) (v : V) :    maxcut_utility G p v =      maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A p v +      maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B p v := by  let P := fun w => G.Adj v w ∧ p w ≠ p v  have hP_univ : maxcut_utility G p v = (Finset.univ.filter P).card := rfl  by_cases hvA : v ∈ A  · by_cases hvB : v ∈ B    · have hvo : v = o := by        have : v ∈ A ∩ B := mem_inter.mpr ⟨hvA, hvB⟩        rw [hinter] at this        exact mem_singleton.mp this      rw [maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq G A p v hvA,          maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq G B p v hvB]      rw [hP_univ]      have hunion : Finset.univ.filter P = (A.filter P) ∪ (B.filter P) := by        rw [← filter_union, hcover]      have hdisj : Disjoint (A.filter P) (B.filter P) := by        rw [disjoint_iff_inter_eq_empty, ← filter_inter_distrib, hinter]        rw [filter_singleton]        split_ifs with hPo        · subst hvo          exact False.elim (G.irrefl hPo.1)        · rfl      rw [hunion, card_union_of_disjoint hdisj]    · have hpayB : maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B p v = 0 := dif_neg hvB      rw [hP_univ, hpayB, add_zero, maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq G A p v hvA]      congr 1      ext w      simp only [mem_filter, mem_univ, true_and]      constructor      · intro hw        have hwA : w ∈ A := by          by_contra hnwA          have hwB : w ∈ B := by            have : w ∈ A ∪ B := by rw [hcover]; exact mem_univ w            exact (mem_union.mp this).resolve_left hnwA          exact hsep v hvA hvB w hwB hnwA hw.1        exact ⟨hwA, hw⟩      · intro hw        exact hw.2  · have hvB : v ∈ B := by      have : v ∈ A ∪ B := by rw [hcover]; exact mem_univ v      exact (mem_union.mp this).resolve_left hvA    have hpayA : maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A p v = 0 := dif_neg hvA    rw [hP_univ, hpayA, zero_add, maxcut_single_vertex_sum_strong_equilibrium_a_payoff_eq G B p v hvB]    congr 1    ext w    simp only [mem_filter, mem_univ, true_and]    constructor    · intro hw      have hwB : w ∈ B := by        by_contra hnwB        have hwA : w ∈ A := by          have : w ∈ A ∪ B := by rw [hcover]; exact mem_univ w          exact (mem_union.mp this).resolve_right hnwB        have : ¬ G.Adj w v := hsep w hwA hnwB v hvB hvA        exact this (G.adj_symm hw.1)      exact ⟨hwB, hw⟩    · intro hw      exact hw.2lemma maxcut_single_vertex_sum_strong_equilibrium_hstable_of_eq    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (A : Finset V) (k : ℕ) (σ : V → Fin k)    (hA : is_maxcut_strong_equilibrium (G.induce (↑A : Set V)) (fun v => σ v.1))    (τ : V → Fin k) (hchanged : ∃ v ∈ (↑A : Set V), τ v ≠ σ v) :    ∃ v ∈ (↑A : Set V), τ v ≠ σ v ∧      maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A τ v ≤      maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A σ v := by  by_contra hnot  have hnot' : ∀ v ∈ (↑A : Set V), τ v ≠ σ v →      maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A σ v <      maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A τ v := by    intro v hv hd    by_contra hle    push Not at hle    exact hnot ⟨v, hv, hd, hle⟩  obtain ⟨v0, hv0A, hd0⟩ := hchanged  let GA := G.induce (↑A : Set V)  let σA : (↑A : Set V) → Fin k := fun v => σ v.1  let τA : (↑A : Set V) → Fin k := fun v => τ v.1  let SA : Finset (↑A : Set V) := Finset.univ.filter (fun v => τA v ≠ σA v)  have hdev : is_maxcut_strong_deviation GA σA SA τA := by    refine ⟨?_, ?_, ?_⟩    · refine ⟨⟨v0, hv0A⟩, ?_⟩      rw [mem_filter]      exact ⟨mem_univ _, hd0⟩    · intro v hv      rw [mem_filter] at hv      push Not at hv      exact hv (mem_univ v)    · intro v hv      rw [mem_filter] at hv      have hne : τ v.1 ≠ σ v.1 := hv.2      have hvA : v.1 ∈ (↑A : Set V) := v.2      have hlt := hnot' v.1 hvA hne      have ha_σ : maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A σ v.1 = maxcut_utility GA σA v := by        dsimp [maxcut_single_vertex_sum_strong_equilibrium_a_payoff]        split_ifs with h        · rfl        · exact False.elim (h v.2)      have ha_τ : maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A τ v.1 = maxcut_utility GA τA v := by        dsimp [maxcut_single_vertex_sum_strong_equilibrium_a_payoff]        split_ifs with h        · rfl        · exact False.elim (h v.2)      rw [ha_σ, ha_τ] at hlt      exact hlt  exact hA SA τA hdevtheorem maxcut_single_vertex_sum_strong_equilibrium    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (A B : Finset V) (o : V) (k : ℕ) (σ : V → Fin k)    (hcover : A ∪ B = Finset.univ) (hinter : A ∩ B = {o})    (hsep : ∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w)    (hA : is_maxcut_strong_equilibrium (G.induce (↑A : Set V)) (fun v => σ v.1))    (hB : is_maxcut_strong_equilibrium (G.induce (↑B : Set V)) (fun v => σ v.1)) :    is_maxcut_strong_equilibrium G σ := by  have hoA : o ∈ (↑A : Set V) := by    have : o ∈ A ∩ B := by rw [hinter]; exact mem_singleton_self o    exact (mem_inter.mp this).1  have hoB : o ∈ (↑B : Set V) := by    have : o ∈ A ∩ B := by rw [hinter]; exact mem_singleton_self o    exact (mem_inter.mp this).2  have hcov : ∀ v, v ∈ (↑A : Set V) ∨ v ∈ (↑B : Set V) := by    intro v    have : v ∈ A ∪ B := by rw [hcover]; exact mem_univ v    exact mem_union.mp this  have hint : ∀ v, v ∈ (↑A : Set V) → v ∈ (↑B : Set V) → v = o := by    intro v hvA hvB    have : v ∈ A ∩ B := mem_inter.mpr ⟨hvA, hvB⟩    rw [hinter] at this    exact mem_singleton.mp this  have ha0 : ∀ (p : V → Fin k) (v : V), v ∉ (↑A : Set V) →      maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A p v = 0 :=    fun p v hv => dif_neg hv  have hb0 : ∀ (p : V → Fin k) (v : V), v ∉ (↑B : Set V) →      maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B p v = 0 :=    fun p v hv => dif_neg hv  have hstabA : ∀ τ, (∃ v, v ∈ (↑A : Set V) ∧ τ v ≠ σ v) →      ∃ v, v ∈ (↑A : Set V) ∧ τ v ≠ σ v ∧        maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A τ v ≤        maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A σ v :=    fun τ h => maxcut_single_vertex_sum_strong_equilibrium_hstable_of_eq G A k σ hA τ h  have hstabB : ∀ τ, (∃ v, v ∈ (↑B : Set V) ∧ τ v ≠ σ v) →      ∃ v, v ∈ (↑B : Set V) ∧ τ v ≠ σ v ∧        maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B τ v ≤        maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B σ v :=    fun τ h => maxcut_single_vertex_sum_strong_equilibrium_hstable_of_eq G B k σ hB τ h  have hglue := maxcut_single_vertex_gluing_abstract σ (↑A : Set V) (↑B : Set V) o    hoA hoB hcov hint    (maxcut_single_vertex_sum_strong_equilibrium_a_payoff G A)    (maxcut_single_vertex_sum_strong_equilibrium_a_payoff G B)    ha0 hb0 hstabA hstabB  intro S τ hdev  rcases hdev with ⟨hne, houtside, hgain⟩  have hdiff : ∃ v, τ v ≠ σ v := by    by_contra hsame    push Not at hsame    obtain ⟨v0, hv0⟩ := hne    have hg := hgain v0 hv0    have hu_eq : maxcut_utility G τ v0 = maxcut_utility G σ v0 := by      dsimp [maxcut_utility]      congr 1      ext w      simp only [mem_filter, mem_univ, true_and]      rw [hsame w, hsame v0]    rw [hu_eq] at hg    exact Nat.lt_irrefl _ hg  obtain ⟨v, hvd, hle⟩ := hglue τ hdiff  have hvS : v ∈ S := by    by_contra hnvS    exact hvd (houtside v hnvS)  have hg := hgain v hvS  rw [maxcut_single_vertex_sum_strong_equilibrium_utility_eq_sum_payoffs G A B o k τ hcover hinter hsep v,      maxcut_single_vertex_sum_strong_equilibrium_utility_eq_sum_payoffs G A B o k σ hcover hinter hsep v] at hg  exact Nat.not_le_of_lt hg hle
See it in the graphDiscuss this resultChallenge it