maxcut_one_double_defect_new_edge_unique
theoremverified
Under a strong deviation from a profile with maximum defect two and at most one defect-two vertex, all newly monochromatic edges coincide as an undirected edge.
Statement
theorem maxcut_one_double_defect_new_edge_unique {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 τ) : ∀ a b c d : V, G.Adj a b → τ a = τ b → σ a ≠ σ b → G.Adj c d → τ c = τ d → σ c ≠ σ d → (a = c ∧ b = d) ∨ (a = d ∧ b = c)
- Source
- Coalitional incidence argument for the one-exception potential, experiment 16419.
- 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 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
set_option maxRecDepth 8192 set_option maxHeartbeats 3000000 theorem maxcut_one_double_defect_new_edge_unique {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 τ) : ∀ a b c d : V, G.Adj a b → τ a = τ b → σ a ≠ σ b → G.Adj c d → τ c = τ d → σ c ≠ σ d → (a = c ∧ b = d) ∨ (a = d ∧ b = c) := by classical have hnorm (a b : V) (hab : G.Adj a b) (ht : τ a = τ b) (hs : σ a ≠ σ b) : ∃ u v : V, ((a = u ∧ b = v) ∨ (a = v ∧ b = u)) ∧ u ∈ C ∧ G.Adj u v ∧ τ v = τ u ∧ (Finset.univ.filter fun w => G.Adj u w ∧ σ w = σ u).card = 2 ∧ (Finset.univ.filter fun w => G.Adj u w ∧ τ w = τ u).card ≤ 1 := by have hon (u v : V) (hu : u ∈ C) (huv : G.Adj u v) (htuv : τ v = τ u) : (Finset.univ.filter fun w => G.Adj u w ∧ σ w = σ u).card = 2 ∧ (Finset.univ.filter fun w => G.Adj u w ∧ τ w = τ u).card ≤ 1 := by have hpos : 0 < (Finset.univ.filter fun w => G.Adj u w ∧ τ w = τ u).card := by apply Finset.card_pos.mpr exact ⟨v, Finset.mem_filter.mpr ⟨Finset.mem_univ v, huv, htuv⟩⟩ have ho := maxcut_utility_add_monochromatic_card G σ u have hn := maxcut_utility_add_monochromatic_card G τ u have hg := hdev.2.2 u hu have hb := hbound u omega by_cases ha : a ∈ C · obtain ⟨ho, hn⟩ := hon a b ha hab ht.symm exact ⟨a, b, Or.inl ⟨rfl, rfl⟩, ha, hab, ht.symm, ho, hn⟩ · have hb : b ∈ C := by by_contra hb apply hs calc σ a = τ a := (hdev.2.1 a ha).symm _ = τ b := ht _ = σ b := hdev.2.1 b hb obtain ⟨ho, hn⟩ := hon b a hb hab.symm ht exact ⟨b, a, Or.inr ⟨rfl, rfl⟩, hb, hab.symm, ht, ho, hn⟩ intro a b c d hab ht hs hcd ht' hs' obtain ⟨u,v,huv,huC,hua,hut,huold,hunew⟩ := hnorm a b hab ht hs obtain ⟨x,y,hxy,hxC,hxa,hxt,hxold,hxnew⟩ := hnorm c d hcd ht' hs' have hux : u = x := hunique u x huold hxold subst x have hvy : v = y := by apply Finset.card_le_one.mp hunew · exact Finset.mem_filter.mpr ⟨Finset.mem_univ v, hua, hut⟩ · exact Finset.mem_filter.mpr ⟨Finset.mem_univ y, hxa, hxt⟩ subst y rcases huv with ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩ <;> rcases hxy with ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩ <;> simp