maxcut_one_double_defect_strict_welfare
theoremverified
If a profile has maximum monochromatic degree two and at most one vertex of degree two, every strong deviation strictly increases social welfare.
Statement
theorem maxcut_one_double_defect_strict_welfare {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (C : Finset V) (hbound : ∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2) (hunique : ∀ u v : V, (Finset.univ.filter fun w => G.Adj u w ∧ σ w = σ u).card = 2 → (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 → u = v) (hdev : is_maxcut_strong_deviation G σ C τ) : maxcut_welfare G σ < maxcut_welfare G τ
- Source
- Equality-case argument from the defect-two strong-deviation welfare identity.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- maxcut_defect_two_deviation_welfare_nondecreasingA strong deviation cannot decrease the cut value when every member of the deviating coalition initially has at most two same-colored…
- maxcut_defect_two_equal_welfare_deviation_structureIf a strong deviation from coalition defect at most two preserves welfare, every deviator has defect two before and one after, every old…
- maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
- 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)…
- 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_one_double_defect_deviation_decreasesIf a coloring has monochromatic degree at most two with at most one vertex of degree two, every strong deviation stays in that class and…
Lean source view module on GitHub
theorem maxcut_one_double_defect_strict_welfare {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (C : Finset V) (hbound : ∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2) (hunique : ∀ u v : V, (Finset.univ.filter fun w => G.Adj u w ∧ σ w = σ u).card = 2 → (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 → u = v) (hdev : is_maxcut_strong_deviation G σ C τ) : maxcut_welfare G σ < maxcut_welfare G τ := by classical have hle := maxcut_defect_two_deviation_welfare_nondecreasing G σ τ C (fun v _ => hbound v) hdev by_contra hn have heq : maxcut_welfare G σ = maxcut_welfare G τ := by omega have hs := maxcut_defect_two_equal_welfare_deviation_structure G σ τ C (fun v _ => hbound v) hdev heq obtain ⟨v, hv⟩ := hdev.1 have hv2 := (hs.1 v hv).1 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 hadj : G.Adj v w := (Finset.mem_filter.mp hw).2.1 have hsame : σ v = σ w := (Finset.mem_filter.mp hw).2.2.symm have hwC : w ∈ C := hs.2.1 v hv w hadj hsame have hw2 := (hs.1 w hwC).1 exact (G.ne_of_adj hadj) (hunique v w hv2 hw2)