AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_of_defect_one

theoremverified

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
Used by 1

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.

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

    lines 7–11

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

    lines 12–18

    uses Finset.mem_univ, Finset.mem_filter.mpr, Finset.mem_filter.mp, Finset.exists_min_image

      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σ⟩
  3. 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).

    lines 19–25

    uses maxcut_defect_one_strong_deviation_mono_decreases, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ

      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⟩
  4. 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.

    lines 26–29

    uses Finset.card_le_card, le_trans, Finset.mem_filter.mpr, Finset.mem_univ

      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τ⟩
  5. 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.

    lines 30–39

    uses Finset.mem_filter.mpr, Finset.mem_univ, Finset.mem_filter.mp, Finset.ssubset_iff_subset_ne.mpr

      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)
  6. 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(σ).

    lines 40–45

    uses Finset.sum_lt_sum, Finset.card_le_card, Finset.mem_univ, Finset.card_lt_card

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

    lines 46–47

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

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