cycle_not_proportionally_two_choosable_of_odd
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
- cycle_not_proportionally_two_choosableFor every integer n ≥ 3, the simple n-cycle C_n is not proportionally 2-choosable: it is not the case that for every finite color palette…
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.
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.
intro HThe 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).
have hcol : (SimpleGraph.cycleGraph n).Colorable 2 := by obtain ⟨f, -, -⟩ := H (Fin 2) (fun _ => Finset.univ) (by simp) exact ⟨f⟩
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.
uses
SimpleGraph.Colorable.chromaticNumber_le,SimpleGraph.chromaticNumber_cycleGraph_of_oddhave 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.
- The proof only uses list-colorability with identical lists of size 2, completely discarding the proportional balance conditions on color frequencies. Because an odd cycle is not even 2-colorable, ordinary chromatic number theory suffices to refute proportional 2-choosability.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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