AFTD Auto-Formalizing Theoretical Domains

cycle_not_proportionally_two_choosable_of_odd

theoremverified

For every odd integer n ≥ 3, the simple n-cycle C_n is not proportionally 2-choosable.

Statement

theorem cycle_not_proportionally_two_choosable_of_odd (n : ℕ) (hn : 3 ≤ n) (hodd : Odd n) :
    ¬ ∀ (α : Type) [Fintype α] [DecidableEq α] (L : Fin n → Finset α),
      (∀ v, (L v).card = 2) →
      ∃ f : (SimpleGraph.cycleGraph n).Coloring α,
        (∀ v, f v ∈ L v) ∧
        ∀ c : α,
          let η := (Finset.univ.filter (fun v => c ∈ L v)).card
          let uses := (Finset.univ.filter (fun v => f v = c)).card
          uses = η / 2 ∨ uses = η ⌈/⌉ 2
Source
step towards cycle_not_proportionally_two_choosable
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof proceeds by contradiction. If an odd cycle C_n (with n ≥ 3) were proportionally 2-choosable, assigning the same 2-element list of colors to every vertex would produce a proper 2-coloring of C_n. Consequently, the chromatic number of C_n would be at most 2. However, every odd cycle has chromatic number 3, yielding the contradiction 3 ≤ 2.

  1. Assume for contradiction that the cycle graph C_n is proportionally 2-choosable.

    To prove the negated statement, we introduce the hypothesis H asserting that C_n is proportionally 2-choosable for any 2-element list assignment, reducing the goal to deriving False.

    line 11

      intro H
  2. The cycle graph C_n is 2-colorable.

    We instantiate hypothesis H with the 2-element color palette Fin 2 and assign every vertex the identical list L(v) = Fin 2. Each list has size 2 (checked by simp). The hypothesis then guarantees the existence of a proper coloring f : V(C_n) → Fin 2 using colors from these lists, which proves that C_n is 2-colorable (hcol).

    lines 13–15

      have hcol : (SimpleGraph.cycleGraph n).Colorable 2 := by
        obtain ⟨f, -, -⟩ := H (Fin 2) (fun _ => Finset.univ) (by simp)
        exact ⟨f⟩
  3. A contradiction: the chromatic number of C_n is at most 2, but equals 3.

    Since C_n is 2-colorable, its chromatic number is at most 2 by SimpleGraph.Colorable.chromaticNumber_le. However, because n ≥ 3 ≥ 2 (verified by omega) and n is odd, SimpleGraph.chromaticNumber_cycleGraph_of_odd proves that the chromatic number of C_n is 3. Substituting this into the inequality produces 3 ≤ 2, which norm_num refutes to conclude the proof.

    lines 18–21

    uses SimpleGraph.Colorable.chromaticNumber_le, SimpleGraph.chromaticNumber_cycleGraph_of_odd

      have hle := SimpleGraph.Colorable.chromaticNumber_le hcol
      have hchrom := SimpleGraph.chromaticNumber_cycleGraph_of_odd n (by omega) hodd
      rw [hchrom] at hle
      norm_num at hle
SimpleGraph.Colorable.chromaticNumber_le
If a graph is n-colorable, then its chromatic number is at most n.
SimpleGraph.chromaticNumber_cycleGraph_of_odd
For every odd integer n ≥ 2, the cycle graph C_n has chromatic number 3.

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

/-- Odd cycles C_n (n ≥ 3) are not proportionally 2-choosable (they are not even 2-colorable). -/theorem cycle_not_proportionally_two_choosable_of_odd (n : ℕ) (hn : 3 ≤ n) (hodd : Odd n) :    ¬ ∀ (α : Type) [Fintype α] [DecidableEq α] (L : Fin n → Finset α),      (∀ v, (L v).card = 2) →      ∃ f : (SimpleGraph.cycleGraph n).Coloring α,        (∀ v, f v ∈ L v) ∧        ∀ c : α,          let η := (Finset.univ.filter (fun v => c ∈ L v)).card          let uses := (Finset.univ.filter (fun v => f v = c)).card          uses = η / 2 ∨ uses = η ⌈/⌉ 2 := by  intro H  -- Use the palette `Fin 2` and give every vertex the full list.  have hcol : (SimpleGraph.cycleGraph n).Colorable 2 := by    obtain ⟨f, -, -⟩ := H (Fin 2) (fun _ => Finset.univ) (by simp)    exact ⟨f⟩  -- A 2-coloring would force the chromatic number to be at most 2,  -- but an odd cycle has chromatic number 3.  have hle := SimpleGraph.Colorable.chromaticNumber_le hcol  have hchrom := SimpleGraph.chromaticNumber_cycleGraph_of_odd n (by omega) hodd  rw [hchrom] at hle  norm_num at hle
See it in the graphDiscuss this resultChallenge it