maxcut_defect_one_strong_deviation_mono_decreases
A strong deviation from a coloring with at most one same-colored neighbor per vertex cannot create a monochromatic edge and must remove at least one.
Statement
theorem maxcut_defect_one_strong_deviation_mono_decreases {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (C : Finset V) (hdefect : ∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1) (hdev : is_maxcut_strong_deviation G σ C τ) : (∀ v w : V, G.Adj v w → τ v = τ w → σ v = σ w) ∧ ∃ v w : V, G.Adj v w ∧ σ v = σ w ∧ τ v ≠ τ w
- Source
- Unweighted Max-k-Cut definitions from arXiv:2610.04948, Section 1; elementary monochromatic-edge exchange.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
- 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_strong_equilibrium_of_defect_oneIf 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…
- maxcut_strong_equilibrium_extension_of_colorable_deletionIf a vertex has degree below twice the number of colors and its deletion is k-colorable, then the original graph has a strong equilibrium…
The proof, explained
For any vertex in the deviation set $C$, the strict increase in utility combined with the identity partition of vertex degree into utility and monochromatic neighbors implies that the vertex has zero same-color neighbors under $\tau$ and at least one under $\sigma$. Consequently, any edge monochromatic under $\tau$ cannot intersect $C$, meaning both endpoints retained their colors from $\sigma$ and no new monochromatic edges are created. Finally, choosing any vertex in the nonempty set $C$ yields an incident edge that was monochromatic under $\sigma$ and becomes bichromatic under $\tau$, eliminating at least one monochromatic edge.
Every vertex in the deviation set $C$ has zero same-color neighbors under the new coloring $\tau$.
For each vertex $v \in C$, the sum of its utility (number of neighbors with a different color) and its monochromatic neighbor count equals its degree under both $\sigma$ and $\tau$. Because $v \in C$, its utility strictly increases under $\tau$. Since $v$ had at most 1 monochromatic neighbor under $\sigma$, linear integer arithmetic implies that under $\tau$ it must have 0 monochromatic neighbors.
uses
maxcut_utility_add_monochromatic_cardclassical have hz : ∀ v ∈ C, (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card = 0 := by intro v hv have h₁ := maxcut_utility_add_monochromatic_card G σ v have h₂ := maxcut_utility_add_monochromatic_card G τ v have hg := hdev.2.2 v hv have hd := hdefect v omega
No vertex in $C$ shares its $\tau$-color with any of its neighbors.
If some neighbor $w$ of $v \in C$ had the same color under $\tau$ ($\tau(w) = \tau(v)$), the set of same-colored neighbors of $v$ would contain $w$, so its cardinality would be strictly positive. This directly contradicts the preceding fact that this cardinality is 0.
uses
Finset.card_pos.mpr,Finset.mem_filter.mpr,Finset.mem_univhave hz' : ∀ v ∈ C, ∀ w, G.Adj v w → τ w ≠ τ v := by intro v hv w hadj heq have hpos : 0 < (Finset.univ.filter fun z => G.Adj v z ∧ τ z = τ v).card := by apply Finset.card_pos.mpr exact ⟨w, Finset.mem_filter.mpr ⟨Finset.mem_univ w, hadj, heq⟩⟩ have hh := hz v hv omega
Any edge that is monochromatic under $\tau$ was already monochromatic under $\sigma$.
We split the goal into the two main conjuncts. Consider an edge with endpoints $v$ and $w$ that has the same color under $\tau$ ($\tau(v) = \tau(w)$). If either $v \in C$ or $w \in C$, this contradicts the previous step showing that vertices in $C$ share no color with their neighbors. Hence neither endpoint is in $C$, so neither changed color from $\sigma$ to $\tau$, yielding $\sigma(v) = \tau(v) = \tau(w) = \sigma(w)$.
constructor · intro v w hadj heq by_cases hv : v ∈ C · exact (hz' v hv w hadj heq.symm).elim by_cases hw : w ∈ C · exact (hz' w hw v (hadj.symm) heq).elim calc σ v = τ v := (hdev.2.1 v hv).symm _ = τ w := heq _ = σ w := hdev.2.1 w hw
There exists an edge that is monochromatic under $\sigma$ but bichromatic under $\tau$.
Because $C$ is nonempty, there is a vertex $v \in C$. Since the utility of $v$ strictly increases from $\sigma$ to $\tau$ while the sum of utility and monochromatic neighbors is the vertex degree, $v$ must have had strictly more than 0 same-color neighbors under $\sigma$. Choosing such a neighbor $w$, the edge $\{v, w\}$ is monochromatic under $\sigma$. By the second step, since $v \in C$, its new color $\tau(v)$ differs from that of all its neighbors, so $\tau(v) \ne \tau(w)$.
uses
maxcut_utility_add_monochromatic_card,Finset.card_pos.mp,Finset.mem_filter.mp,Ne.symm· obtain ⟨v, hv⟩ := hdev.1 have h₁ := maxcut_utility_add_monochromatic_card G σ v have h₂ := maxcut_utility_add_monochromatic_card G τ v have hg := hdev.2.2 v hv have hpos : 0 < (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := by omega obtain ⟨w, hw⟩ := Finset.card_pos.mp hpos have hw' := Finset.mem_filter.mp hw refine ⟨v, w, hw'.2.1, hw'.2.2.symm, ?_⟩ exact Ne.symm (hz' v hv w hw'.2.1)
maxcut_utility_add_monochromatic_card- For any vertex $v$ and coloring $\sigma$, the utility of $v$ (the number of neighbors with a different color) plus the number of neighbors with the same color equals the degree of $v$.
Finset.card_pos.mpr- A finite set has strictly positive cardinality if it is nonempty.
Finset.mem_filter.mpr- An element belongs to a filtered subset if it belongs to the ambient set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal set `Finset.univ`.
Finset.card_pos.mp- If a finite set has strictly positive cardinality, then it is nonempty.
Finset.mem_filter.mp- If an element belongs to a filtered subset, then it belongs to the ambient set and satisfies the predicate.
Ne.symm- Inequality is symmetric: if $a \neq b$, then $b \neq a$.
- The linear arithmetic solver `omega` is used at several points to deduce inequalities and equalities on monochromatic neighbor counts from the degree-utility identity.
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_defect_one_strong_deviation_mono_decreases {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (C : Finset V) (hdefect : ∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 1) (hdev : is_maxcut_strong_deviation G σ C τ) : (∀ v w : V, G.Adj v w → τ v = τ w → σ v = σ w) ∧ ∃ v w : V, G.Adj v w ∧ σ v = σ w ∧ τ v ≠ τ w := by classical have hz : ∀ v ∈ C, (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card = 0 := by intro v hv have h₁ := maxcut_utility_add_monochromatic_card G σ v have h₂ := maxcut_utility_add_monochromatic_card G τ v have hg := hdev.2.2 v hv have hd := hdefect v omega have hz' : ∀ v ∈ C, ∀ w, G.Adj v w → τ w ≠ τ v := by intro v hv w hadj heq have hpos : 0 < (Finset.univ.filter fun z => G.Adj v z ∧ τ z = τ v).card := by apply Finset.card_pos.mpr exact ⟨w, Finset.mem_filter.mpr ⟨Finset.mem_univ w, hadj, heq⟩⟩ have hh := hz v hv omega constructor · intro v w hadj heq by_cases hv : v ∈ C · exact (hz' v hv w hadj heq.symm).elim by_cases hw : w ∈ C · exact (hz' w hw v (hadj.symm) heq).elim calc σ v = τ v := (hdev.2.1 v hv).symm _ = τ w := heq _ = σ w := hdev.2.1 w hw · obtain ⟨v, hv⟩ := hdev.1 have h₁ := maxcut_utility_add_monochromatic_card G σ v have h₂ := maxcut_utility_add_monochromatic_card G τ v have hg := hdev.2.2 v hv have hpos : 0 < (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := by omega obtain ⟨w, hw⟩ := Finset.card_pos.mp hpos have hw' := Finset.mem_filter.mp hw refine ⟨v, w, hw'.2.1, hw'.2.2.symm, ?_⟩ exact Ne.symm (hz' v hv w hw'.2.1)