maxcut_strong_equilibrium_of_saturated_vertex
A coloring of a finite graph is a strong equilibrium if its restriction after deleting a vertex is a strong equilibrium and every edge incident to the deleted vertex is cut by the coloring.
Statement
theorem maxcut_strong_equilibrium_of_saturated_vertex {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) {k : ℕ} (σ : V → Fin k) (hproper : ∀ w, G.Adj v w → σ w ≠ σ v) (hsub : is_maxcut_strong_equilibrium (G.induce (↑(Finset.univ.erase v) : Set V)) (fun x => σ x.1)) : is_maxcut_strong_equilibrium G σ
- Source
- Structural reduction for OP-85, the unweighted Max-k-Cut strong-equilibrium existence problem in arXiv:2610.04948, Section 4.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- maxcut_utility_le_degreeA player's utility in the Max-k-Cut game never exceeds its degree: the neighbours cut away by v form a subset of the neighbours of v.
- maxcut_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
- 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 1
- maxcut_strong_equilibrium_extend_low_degree_vertexIf a vertex has degree strictly smaller than the number k of available colors, a strong equilibrium of the induced graph obtained by…
The proof, explained
The theorem is proved by contradiction: suppose a coalition S has a profitable strong deviation τ in G. Because every edge incident to v is cut under σ, v already achieves its maximum possible cut utility (its degree) and therefore cannot belong to S. Restricting the coalition to the remaining vertices A = V \ {v} yields a nonempty coalition S' on G[A]. Decomposing the cut utility of each vertex in A into its internal edges in G[A] and its edge to v shows that the edge to v contributes at least as much to the utility under σ as under τ, so every vertex in S' must also strictly improve its utility within G[A], contradicting the assumption that the restricted coloring is a strong equilibrium.
Define the set A of all vertices other than v.
We work classically and define the finite set A = V \ {v}, which corresponds to the vertex set of the induced subgraph after deleting v.
classical let A : Finset V := Finset.univ.erase vUnder the coloring σ, vertex v achieves the maximum possible cut utility, equal to its degree.
By the hypothesis hproper, every neighbor of v receives a color distinct from σ(v), so the set of neighbors sharing v's color is empty (Finset.filter_eq_empty_iff.mpr). Since cut utility plus the number of monochromatic neighbors equals the vertex degree (maxcut_utility_add_monochromatic_card), v's cut utility under σ is exactly deg(v).
uses
Finset.filter_eq_empty_iff.mpr,maxcut_utility_add_monochromatic_cardhave hfull : maxcut_utility G σ v = G.degree v := by have hz : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v) = ∅ := by apply Finset.filter_eq_empty_iff.mpr intro w _ ⟨hw, heq⟩ exact hproper w hw heq have h := maxcut_utility_add_monochromatic_card G σ v simpa [hz] using h
For any coloring p and any vertex x ∈ A, the cut utility of x in G decomposes into its cut utility in G[A] plus an indicator for the edge between x and v.
For a vertex x ∈ A, let P(w) be the condition that w is adjacent to x and p(w) ≠ p(x). Since the vertex set of G partitions into A and {v} with v ∉ A, the neighbors of x satisfying P partition into those in A and, if P(v) holds, the vertex v itself (Finset.filter_insert). Rewriting the count over A as the cut utility in the induced subgraph G[A] via the subtype cardinality equivalence maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype yields the decomposition.
uses
Finset.filter_insert,maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtypehave hsplit : ∀ (p : V → Fin k) (x : V) (hx : x ∈ A), maxcut_utility G p x = maxcut_utility (G.induce (↑A : Set V)) (fun y => p y.1) ⟨x,hx⟩ + if G.Adj x v ∧ p v ≠ p x then 1 else 0 := by intro p x hx let P : V → Prop := fun w => G.Adj x w ∧ p w ≠ p x have hcard : (Finset.univ.filter P).card = (A.filter P).card + if P v then 1 else 0 := by have huniv : insert v A = Finset.univ := by simp [A] have hnot : v ∉ A.filter P := by simp [A] rw [← huniv, Finset.filter_insert] by_cases hp : P v <;> simp [hp, hnot] have hsubcard := maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype A P change (Finset.univ.filter P).card = (Finset.univ.filter (fun y : (↑A : Set V) => P y.1)).card + if P v then 1 else 0 rw [hsubcard] exact hcard
No strong deviation (S, τ) from σ in G can contain the vertex v.
Suppose for contradiction that (S, τ) is a strong deviation in G. If v were in S, then v would strictly improve its cut utility, giving u_G(τ, v) > u_G(σ, v) = deg(v). But a vertex's cut utility can never exceed its degree (maxcut_utility_le_degree), yielding an arithmetic contradiction via omega. Thus v ∉ S.
uses
maxcut_utility_le_degreeintro S τ hdev have hvS : v ∉ S := by intro hv have hg := hdev.2.2 v hv have hu := maxcut_utility_le_degree G τ v omega
The restriction of the deviating coalition S to A, denoted S', is nonempty.
We define S' as the subset of A consisting of those vertices that belong to S. Since (S, τ) is a strong deviation, S is nonempty, so it contains some vertex x. Because v ∉ S, x ≠ v, so x ∈ A, which means S' is nonempty.
let S' : Finset (↑A : Set V) := Finset.univ.filter (fun x => x.1 ∈ S) have hdev' : is_maxcut_strong_deviation (G.induce (↑A : Set V)) (fun x => σ x.1) S' (fun x => τ x.1) := by refine ⟨?_, ?_, ?_⟩ · obtain ⟨x, hx⟩ := hdev.1 have hxne : x ≠ v := by intro h; subst x; exact hvS hx exact ⟨⟨x, by simp [A, hxne]⟩, by simp [S', hx]⟩
Vertices outside S' retain their original colors under τ|_A.
Any vertex x ∈ A not in S' does not belong to S. Because τ is a deviation on G, it leaves all vertices outside S unchanged, so τ(x) = σ(x).
· intro x hx have hxS : x.1 ∉ S := by simpa [S'] using hx exact hdev.2.1 x.1 hxS
Every vertex in S' strictly increases its cut utility in G[A] under τ|_A, establishing that (S', τ|_A) is a strong deviation in G[A].
For any x ∈ S', we have x ∈ S, so x strictly improves its cut utility in G: u_G(σ, x) < u_G(τ, x). By the utility decomposition formula hsplit, this means u_{G[A]}(σ|_A, x) + 1_σ < u_{G[A]}(τ|_A, x) + 1_τ, where 1_p indicates whether the edge {x, v} is cut by p. If x is adjacent to v, then by symmetry of adjacency (G.adj_symm) and inequality symmetry (Ne.symm), the hypothesis that all edges incident to v are cut under σ guarantees σ(v) ≠ σ(x), making 1_σ = 1 while 1_τ ≤ 1 (simplified via true_and and if_true); if x is not adjacent to v, both indicators are 0. In either case 1_τ ≤ 1_σ, which implies u_{G[A]}(σ|_A, x) < u_{G[A]}(τ|_A, x).
uses
Ne.symm,G.adj_symm,true_and,if_true· rintro ⟨x, hxA⟩ hx have hxS : x ∈ S := by simpa [S'] using hx have hg := hdev.2.2 x hxS have ha : (if G.Adj x v ∧ τ v ≠ τ x then 1 else 0 : ℕ) ≤ (if G.Adj x v ∧ σ v ≠ σ x then 1 else 0 : ℕ) := by by_cases hadj : G.Adj x v · have hp : σ v ≠ σ x := Ne.symm (hproper x (G.adj_symm hadj)) simp only [hadj, hp, true_and, if_true] split <;> omega · simp [hadj] rw [hsplit σ x hxA, hsplit τ x hxA] at hg omegaThe existence of the strong deviation (S', τ|_A) contradicts the assumption that σ|_A is a strong equilibrium in G[A].
Applying the hypothesis hsub (that the restriction of σ to G[A] is a strong equilibrium) to the deviation (S', τ|_A) produces False, which completes the proof that σ is a strong equilibrium in G.
exact hsub S' (fun x => τ x.1) hdev'
Finset.filter_eq_empty_iff.mpr- A filtered finite set is empty if no element satisfies the filtering predicate.
maxcut_utility_add_monochromatic_card- For any vertex in a simple graph, its cut utility plus the number of its monochromatic incident edges equals its degree.
Finset.filter_insert- Filtering an inserted element into a finite set adds the element if it satisfies the predicate, and leaves the filtered set unchanged otherwise.
maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype- The number of elements satisfying a predicate in a subtype of a finite set equals the cardinality of the filtered subset in the ambient set.
maxcut_utility_le_degree- The cut utility of any vertex under any coloring cannot exceed the degree of that vertex.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
G.adj_symm- Adjacency in a simple graph is symmetric: if x is adjacent to v, then v is adjacent to x.
true_and- The logical conjunction True ∧ p simplifies to p.
if_true- A conditional expression whose branch condition is True simplifies to its 'then' branch.
- In Lean, induced subgraphs are formalized using subtypes (here `SimpleGraph.induce (↑(Finset.univ.erase v) : Set V) G`), which requires bridging finite-set card filter expressions on the ambient type `V` with card filter expressions on the subtype via `maxcut_single_vertex_sum_strong_equilibrium_card_filter_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_of_saturated_vertex {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) {k : ℕ} (σ : V → Fin k) (hproper : ∀ w, G.Adj v w → σ w ≠ σ v) (hsub : is_maxcut_strong_equilibrium (G.induce (↑(Finset.univ.erase v) : Set V)) (fun x => σ x.1)) : is_maxcut_strong_equilibrium G σ := by classical let A : Finset V := Finset.univ.erase v have hfull : maxcut_utility G σ v = G.degree v := by have hz : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v) = ∅ := by apply Finset.filter_eq_empty_iff.mpr intro w _ ⟨hw, heq⟩ exact hproper w hw heq have h := maxcut_utility_add_monochromatic_card G σ v simpa [hz] using h have hsplit : ∀ (p : V → Fin k) (x : V) (hx : x ∈ A), maxcut_utility G p x = maxcut_utility (G.induce (↑A : Set V)) (fun y => p y.1) ⟨x,hx⟩ + if G.Adj x v ∧ p v ≠ p x then 1 else 0 := by intro p x hx let P : V → Prop := fun w => G.Adj x w ∧ p w ≠ p x have hcard : (Finset.univ.filter P).card = (A.filter P).card + if P v then 1 else 0 := by have huniv : insert v A = Finset.univ := by simp [A] have hnot : v ∉ A.filter P := by simp [A] rw [← huniv, Finset.filter_insert] by_cases hp : P v <;> simp [hp, hnot] have hsubcard := maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype A P change (Finset.univ.filter P).card = (Finset.univ.filter (fun y : (↑A : Set V) => P y.1)).card + if P v then 1 else 0 rw [hsubcard] exact hcard intro S τ hdev have hvS : v ∉ S := by intro hv have hg := hdev.2.2 v hv have hu := maxcut_utility_le_degree G τ v omega let S' : Finset (↑A : Set V) := Finset.univ.filter (fun x => x.1 ∈ S) have hdev' : is_maxcut_strong_deviation (G.induce (↑A : Set V)) (fun x => σ x.1) S' (fun x => τ x.1) := by refine ⟨?_, ?_, ?_⟩ · obtain ⟨x, hx⟩ := hdev.1 have hxne : x ≠ v := by intro h; subst x; exact hvS hx exact ⟨⟨x, by simp [A, hxne]⟩, by simp [S', hx]⟩ · intro x hx have hxS : x.1 ∉ S := by simpa [S'] using hx exact hdev.2.1 x.1 hxS · rintro ⟨x, hxA⟩ hx have hxS : x ∈ S := by simpa [S'] using hx have hg := hdev.2.2 x hxS have ha : (if G.Adj x v ∧ τ v ≠ τ x then 1 else 0 : ℕ) ≤ (if G.Adj x v ∧ σ v ≠ σ x then 1 else 0 : ℕ) := by by_cases hadj : G.Adj x v · have hp : σ v ≠ σ x := Ne.symm (hproper x (G.adj_symm hadj)) simp only [hadj, hp, true_and, if_true] split <;> omega · simp [hadj] rw [hsplit σ x hxA, hsplit τ x hxA] at hg omega exact hsub S' (fun x => τ x.1) hdev'