maxcut_strong_equilibrium_of_defect_one
If a finite unweighted graph admits a k-coloring in which each vertex has at most one same-colored neighbor, it admits a strong k-color equilibrium, also with at most one same-colored neighbor per vertex.
Statement
theorem maxcut_strong_equilibrium_of_defect_one {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (h : ∃ σ : V → Fin k, ∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1) : ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ ∧ ∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1
- Source
- Elementary finite potential argument for unweighted Max-k-Cut; definitions in arXiv:2610.04948, Section 1.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- maxcut_defect_one_strong_deviation_mono_decreasesA strong deviation from a coloring with at most one same-colored neighbor per vertex cannot create a monochromatic edge and must remove at…
- 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…
- Used by 1
- maxcut_defect_one_dense_core_witnessA 12-vertex graph of minimum degree nine has a six-clique, a 1-defective 3-coloring, and a strong 3-color equilibrium.
The proof, explained
The proof uses a potential function argument on the finite set A of k-colorings that have defect at most 1. We choose a coloring σ ∈ A that minimizes the total monochromatic degree score(ρ) = ∑_v |M(ρ, v)|. If there were a strong deviation by some coalition to a coloring τ, a structural lemma (maxcut_defect_one_strong_deviation_mono_decreases) ensures that monochromatic edges can only be destroyed and at least one is destroyed. Consequently, τ also has defect at most 1 and has a strictly smaller score than σ, contradicting the choice of σ as a score minimizer.
Define the monochromatic neighborhood of each vertex, the total monochromatic score, and the finite set A of colorings with defect at most 1.
For a k-coloring ρ and vertex v, M(ρ, v) is the set of neighbors of v that share its color under ρ. The score of ρ is defined as the total number of monochromatic endpoint-vertex pairs, ∑_v |M(ρ, v)| (twice the number of monochromatic edges). The set A is defined as the set of all colorings ρ where each vertex has at most one monochromatic neighbor (|M(ρ, v)| ≤ 1 for all v).
classical let M (ρ : V → Fin k) (v : V) : Finset V := Finset.univ.filter fun w => G.Adj v w ∧ ρ w = ρ v let score (ρ : V → Fin k) : ℕ := ∑ v : V, (M ρ v).card let A : Finset (V → Fin k) := Finset.univ.filter fun ρ => ∀ v, (M ρ v).card ≤ 1
Choose a coloring σ ∈ A that minimizes the score function.
Hypothesis h provides an initial coloring with defect at most 1, making A nonempty. Because A is a finite nonempty set, Finset.exists_min_image guarantees the existence of a coloring σ ∈ A that minimizes the score on A. Since σ ∈ A, its defect is at most 1, so to prove the theorem it suffices to show that σ is a strong equilibrium.
uses
Finset.mem_univ,Finset.mem_filter.mpr,Finset.mem_filter.mp,Finset.exists_min_imageobtain ⟨ρ, hρ⟩ := h have hA : A.Nonempty := by refine ⟨ρ, Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩⟩ exact hρ obtain ⟨σ, hσA, hmin⟩ := Finset.exists_min_image A score hA have hσ : ∀ v, (M σ v).card ≤ 1 := (Finset.mem_filter.mp hσA).2 refine ⟨σ, ?_, hσ⟩
For any strong coalition deviation τ from σ, every monochromatic neighbor under τ was already monochromatic under σ: M(τ, v) ⊆ M(σ, v) for all v.
Suppose for contradiction that a coalition C can strongly deviate from σ to a coloring τ. By the structural lemma maxcut_defect_one_strong_deviation_mono_decreases, if two adjacent vertices share a color under τ, they must have already shared that color under σ. Therefore, every vertex w ∈ M(τ, v) also belongs to M(σ, v), showing M(τ, v) ⊆ M(σ, v).
uses
maxcut_defect_one_strong_deviation_mono_decreases,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univintro C τ hdev have step := maxcut_defect_one_strong_deviation_mono_decreases G σ τ C hσ hdev have hsub : ∀ v, M τ v ⊆ M σ v := by intro v w hw have hw' : G.Adj v w ∧ τ w = τ v := (Finset.mem_filter.mp hw).2 have heq : σ w = σ v := (step.1 v w hw'.1 hw'.2.symm).symm exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hw'.1, heq⟩
The deviated coloring τ also has defect at most 1, so τ ∈ A.
Because M(τ, v) ⊆ M(σ, v), Finset.card_le_card and le_trans imply that |M(τ, v)| ≤ |M(σ, v)| ≤ 1 for every vertex v. Hence τ satisfies the defect condition and belongs to A.
uses
Finset.card_le_card,le_trans,Finset.mem_filter.mpr,Finset.mem_univhave hτ : ∀ v, (M τ v).card ≤ 1 := by intro v exact le_trans (Finset.card_le_card (hsub v)) (hσ v) have hτA : τ ∈ A := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hτ⟩
There exists a vertex v whose monochromatic neighborhood strictly shrinks: M(τ, v) ⊂ M(σ, v).
The second conclusion of maxcut_defect_one_strong_deviation_mono_decreases provides adjacent vertices v and w such that σ(v) = σ(w) but τ(v) ≠ τ(w). Thus w ∈ M(σ, v) but w ∉ M(τ, v). Combined with the inclusion M(τ, v) ⊆ M(σ, v), this shows M(τ, v) ≠ M(σ, v), so the subset inclusion is strict by Finset.ssubset_iff_subset_ne.mpr.
uses
Finset.mem_filter.mpr,Finset.mem_univ,Finset.mem_filter.mp,Finset.ssubset_iff_subset_ne.mprobtain ⟨v, w, hvw, hold, hnew⟩ := step.2 have hmemold : w ∈ M σ v := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hvw, hold.symm⟩ have hmemnew : w ∉ M τ v := by intro hw exact hnew ((Finset.mem_filter.mp hw).2.2.symm) have hstrict : M τ v ⊂ M σ v := by apply Finset.ssubset_iff_subset_ne.mpr refine ⟨hsub v, ?_⟩ intro heq exact hmemnew (heq.symm ▸ hmemold)
The score of τ is strictly less than the score of σ.
By Finset.card_le_card, |M(τ, i)| ≤ |M(σ, i)| for every vertex i. At the vertex v identified in the previous step, Finset.card_lt_card gives |M(τ, v)| < |M(σ, v)|. Applying Finset.sum_lt_sum across all vertices shows that ∑_v |M(τ, v)| < ∑_v |M(σ, v)|, which means score(τ) < score(σ).
uses
Finset.sum_lt_sum,Finset.card_le_card,Finset.mem_univ,Finset.card_lt_cardhave hs : score τ < score σ := by dsimp [score] apply Finset.sum_lt_sum · intro i hi exact Finset.card_le_card (hsub i) · exact ⟨v, Finset.mem_univ _, Finset.card_lt_card hstrict⟩
A contradiction is reached between the minimality of σ and the strict decrease in score. automation
Since τ ∈ A and σ minimizes the score on A, we have score(σ) ≤ score(τ). But this contradicts score(τ) < score(σ), and the linear arithmetic decision procedure omega derives False to close the goal.
have hm := hmin τ hτA omega
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.mem_filter.mpr- An element belongs to `Finset.filter p s` if it belongs to `s` and satisfies `p`.
Finset.mem_filter.mp- If an element belongs to `Finset.filter p s`, then it belongs to `s` and satisfies `p`.
Finset.exists_min_image- Every nonempty finite set contains an element minimizing a given real- or integer-valued function.
maxcut_defect_one_strong_deviation_mono_decreases- Under any strong deviation from a defect-at-most-1 coloring, monochromatic edges can only be broken (never created), and at least one monochromatic edge is strictly broken.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Finset.ssubset_iff_subset_ne.mpr- If s ⊆ t and s ≠ t, then s is a strict subset of t (s ⊂ t).
Finset.sum_lt_sum- If f(i) ≤ g(i) for all elements of a finite set and f(i) < g(i) for at least one element, then ∑ f(i) < ∑ g(i).
Finset.card_lt_card- If a finite set s is a strict subset of t, then |s| < |t|.
- In step 7, Lean's linear arithmetic tactic `omega` finishes the proof by detecting the contradiction between `score τ < score σ` and `score σ ≤ score τ`.
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.
theorem maxcut_strong_equilibrium_of_defect_one {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (h : ∃ σ : V → Fin k, ∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1) : ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ ∧ ∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1 := by classical let M (ρ : V → Fin k) (v : V) : Finset V := Finset.univ.filter fun w => G.Adj v w ∧ ρ w = ρ v let score (ρ : V → Fin k) : ℕ := ∑ v : V, (M ρ v).card let A : Finset (V → Fin k) := Finset.univ.filter fun ρ => ∀ v, (M ρ v).card ≤ 1 obtain ⟨ρ, hρ⟩ := h have hA : A.Nonempty := by refine ⟨ρ, Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩⟩ exact hρ obtain ⟨σ, hσA, hmin⟩ := Finset.exists_min_image A score hA have hσ : ∀ v, (M σ v).card ≤ 1 := (Finset.mem_filter.mp hσA).2 refine ⟨σ, ?_, hσ⟩ intro C τ hdev have step := maxcut_defect_one_strong_deviation_mono_decreases G σ τ C hσ hdev have hsub : ∀ v, M τ v ⊆ M σ v := by intro v w hw have hw' : G.Adj v w ∧ τ w = τ v := (Finset.mem_filter.mp hw).2 have heq : σ w = σ v := (step.1 v w hw'.1 hw'.2.symm).symm exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hw'.1, heq⟩ have hτ : ∀ v, (M τ v).card ≤ 1 := by intro v exact le_trans (Finset.card_le_card (hsub v)) (hσ v) have hτA : τ ∈ A := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hτ⟩ obtain ⟨v, w, hvw, hold, hnew⟩ := step.2 have hmemold : w ∈ M σ v := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hvw, hold.symm⟩ have hmemnew : w ∉ M τ v := by intro hw exact hnew ((Finset.mem_filter.mp hw).2.2.symm) have hstrict : M τ v ⊂ M σ v := by apply Finset.ssubset_iff_subset_ne.mpr refine ⟨hsub v, ?_⟩ intro heq exact hmemnew (heq.symm ▸ hmemold) have hs : score τ < score σ := by dsimp [score] apply Finset.sum_lt_sum · intro i hi exact Finset.card_le_card (hsub i) · exact ⟨v, Finset.mem_univ _, Finset.card_lt_card hstrict⟩ have hm := hmin τ hτA omega#print axioms maxcut_defect_one_strong_deviation_mono_decreases