AFTD Auto-Formalizing Theoretical Domains

maxcut_defect_one_strong_deviation_mono_decreases

theoremverified

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

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.

  1. 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.

    lines 8–15

    uses maxcut_utility_add_monochromatic_card

      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
  2. 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.

    lines 16–22

    uses Finset.card_pos.mpr, Finset.mem_filter.mpr, Finset.mem_univ

      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
  3. 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)$.

    lines 23–32

      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
  4. 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)$.

    lines 33–41

    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$.

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

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)
See it in the graphDiscuss this resultChallenge it