maxcut_single_vertex_sum_strong_equilibrium
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
- 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_strong_equilibrium_of_saturated_vertexA coloring of a finite graph is a strong equilibrium if its restriction after deleting a vertex is a strong equilibrium and every edge…
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.
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⟩.
uses
Finset.card_bij,mem_filter,mem_univ,true_and,Subtype.extapply 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]
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.
uses
dif_pos,maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtypedsimp [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)
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.
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_disjointlet 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]
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.
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
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.
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
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].
uses
mem_filter,mem_univ,False.elimby_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
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.
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_abstracthave 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
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.
uses
mem_filter,mem_univ,true_and,Nat.lt_irreflintro 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
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.
uses
maxcut_single_vertex_sum_strong_equilibrium_utility_eq_sum_payoffs,Nat.not_le_of_ltobtain ⟨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
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 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