AFTD Auto-Formalizing Theoretical Domains

maxcut_complete_graph_optimal_balanced

theoremverified

In an optimal k-colouring of the complete graph K_n, any two colour classes differ in size by at most one: a vertex whose class has a vertices has a - 1 monochromatic neighbours, and maxcut_optimal_same_color_le says that this is at most the number of neighbours of any other colour, i.e. at most the size of any other class.

Statement

theorem maxcut_complete_graph_optimal_balanced {n k : ℕ} (σ : Fin n → Fin k) (hopt : is_maxcut_optimal (⊤ : SimpleGraph (Fin n)) σ) : ∀ c c' : Fin k, (Finset.univ.filter fun v => σ v = c).card ≤ (Finset.univ.filter fun v => σ v = c').card + 1
Source
step towards maxcut_op89_optimal_strong_equilibrium_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
  • maxcut_optimal_same_color_leAt an optimal coloring σ of the Max-k-Cut game, for every vertex v and every color c, the number of neighbours of v with color σ(v) is at…
Used by 1

Lean source view module on GitHub

/-- Optimal colourings of the complete graph are balanced: colour class sizes differ by at most one. -/
theorem maxcut_complete_graph_optimal_balanced {n k : ℕ} (σ : Fin n → Fin k) (hopt : is_maxcut_optimal (⊤ : SimpleGraph (Fin n)) σ) : ∀ c c' : Fin k, (Finset.univ.filter fun v => σ v = c).card ≤ (Finset.univ.filter fun v => σ v = c').card + 1 := by
  intro c c'
  by_cases h : ∃ v, σ v = c
  · rcases h with ⟨v, hv⟩
    have h1 := maxcut_optimal_same_color_le (⊤ : SimpleGraph (Fin n)) σ hopt v c'
    rw [hv] at h1
    have h_erase : (Finset.univ.filter fun w => (⊤ : SimpleGraph (Fin n)).Adj v w ∧ σ w = c) =
        (Finset.univ.filter fun w => σ w = c).erase v := by
      ext w
      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, SimpleGraph.top_adj]
      tauto
    have h_card_erase : ((Finset.univ.filter fun w => σ w = c).erase v).card =
        (Finset.univ.filter fun w => σ w = c).card - 1 := by
      apply Finset.card_erase_of_mem
      simp [hv]
    have h_le : (Finset.univ.filter fun w => (⊤ : SimpleGraph (Fin n)).Adj v w ∧ σ w = c').card ≤
        (Finset.univ.filter fun w => σ w = c').card := by
      apply Finset.card_le_card
      intro w
      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
      intro hw
      exact hw.2
    rw [h_erase, h_card_erase] at h1
    omega
  · have h_empty : (Finset.univ.filter fun v => σ v = c).card = 0 := by
      have : (Finset.univ.filter fun v => σ v = c) = ∅ := by
        rw [Finset.filter_eq_empty_iff]
        intro x _ hx
        exact h ⟨x, hx⟩
      rw [this, Finset.card_empty]
    omega
See it in the graphDiscuss this resultChallenge it