odd_antihole_chromaticNumber
For ℓ ≥ 3 the odd antihole complement(C_{2ℓ-1}) has chromatic number ℓ.
Statement
theorem odd_antihole_chromaticNumber (ℓ : ℕ) (hℓ : 3 ≤ ℓ) :
(SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.chromaticNumber = ℓ- Source
- arXiv:2610.14241 (Restricting odd antiholes in critical graphs via list coloring), Sec. 2 (the ℓ-chromatic odd antihole); the first conjunct of strong ℓ-chromatic-choosability in OP-216
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- odd_antihole_not_colorable_of_identical_listsFor ℓ ≥ 3, the odd antihole complement(C_{2ℓ-1}) has no proper coloring from identical lists of size ℓ-1: the exception in strong…
The proof, explained
To show that the odd antihole (C_{2ℓ - 1})ᶜ has chromatic number ℓ for ℓ ≥ 3, the proof shows that the graph is ℓ-colorable and not (ℓ - 1)-colorable. An explicit ℓ-coloring is given by u ↦ ⌊u / 2⌋; any two distinct vertices receiving the same color must differ by 1, making them adjacent in the cycle C_{2ℓ - 1} and thus non-adjacent in its complement. Non-(ℓ - 1)-colorability follows from a known theorem establishing that the odd antihole cannot be colored from identical lists of ℓ - 1 colors. The equivalence between having chromatic number ℓ and being ℓ-colorable but not (ℓ - 1)-colorable then completes the argument.
In a cycle graph C_N with N ≥ 3, any two vertices u and v satisfying u + 1 = v are adjacent.
We write N as M + 2 because N ≥ 3. In the cycle graph C_{M+2}, vertices are adjacent if their difference in modular arithmetic is 1 or -1. Unfolding modular subtraction in Fin, the difference v - u is given by ((M + 2 - u) + v) % (M + 2). Substituting v = u + 1 gives (M + 2 + 1) % (M + 2), which reduces to 1 % (M + 2) = 1 since 1 < M + 2. Thus v - u = 1, so u and v are adjacent.
uses
SimpleGraph.cycleGraph_adj,Fin.sub_def,Fin.val_mk,Fin.val_one,Nat.add_mod_left,Nat.mod_eq_of_ltobtain ⟨M, rfl⟩ : ∃ M, N = M + 2 := ⟨N - 2, by omega⟩ rw [SimpleGraph.cycleGraph_adj] right rw [Fin.sub_def] ext simp only [Fin.val_mk, Fin.val_one] have hv := v.isLt rw [show M + 2 - u.val + v.val = (M + 2) + 1 by omega] rw [Nat.add_mod_left] exact Nat.mod_eq_of_lt (by omega)
The odd antihole (C_{2ℓ - 1})ᶜ is ℓ-colorable.
We define a coloring assigning to each vertex u the color ⌊u / 2⌋ in Fin ℓ, which is strictly less than ℓ because u < 2ℓ - 1. Suppose for contradiction that two vertices u and v are adjacent in the complement graph (C_{2ℓ - 1})ᶜ and share the same color. By definition of the complement graph, u ≠ v and u, v are not adjacent in C_{2ℓ - 1}. However, having the same color means ⌊u / 2⌋ = ⌊v / 2⌋; together with u ≠ v, this forces |u - v| = 1 (either u + 1 = v or v + 1 = u). By the auxiliary lemma, such consecutive vertices are adjacent in C_{2ℓ - 1}, contradicting the non-adjacency in the cycle graph. Thus the coloring is proper.
uses
SimpleGraph.Coloring.mk,SimpleGraph.compl_adj,congrArg,Fin.ext,odd_antihole_chromaticNumber_aux_adjhave hcol : (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Colorable ℓ := by refine ⟨SimpleGraph.Coloring.mk (fun u => (⟨u.val / 2, by have := u.isLt; omega⟩ : Fin ℓ)) ?_⟩ intro u v huv heq rw [SimpleGraph.compl_adj] at huv obtain ⟨hne, hnadj⟩ := huv have h2 : u.val / 2 = v.val / 2 := by simpa using congrArg Fin.val heq have hne' : u.val ≠ v.val := fun h => hne (Fin.ext h) rcases (show u.val + 1 = v.val ∨ v.val + 1 = u.val by omega) with h | h · exact hnadj (odd_antihole_chromaticNumber_aux_adj (by omega) u v h) · exact hnadj (odd_antihole_chromaticNumber_aux_adj (by omega) v u h).symm
The odd antihole (C_{2ℓ - 1})ᶜ is not (ℓ - 1)-colorable.
Suppose for contradiction that there is a proper coloring f using ℓ - 1 colors. Then f defines a proper coloring whose palette is the set {0, …, ℓ - 2} of size ℓ - 1. But odd_antihole_not_colorable_of_identical_lists proves that no proper coloring of (C_{2ℓ - 1})ᶜ exists when all vertices must choose from the same list of ℓ - 1 colors. This contradiction shows that the graph cannot be colored with ℓ - 1 colors.
uses
odd_antihole_not_colorable_of_identical_lists,Fin.exthave hnot : ¬ (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Colorable (ℓ - 1) := by rintro ⟨f⟩ apply odd_antihole_not_colorable_of_identical_lists ℓ hℓ (Finset.range (ℓ - 1)) (by simp) refine ⟨fun v => (f v).val, fun v => by simp, ?_⟩ intro u v huv h exact f.valid huv (Fin.ext h)
The chromatic number of (C_{2ℓ - 1})ᶜ is ℓ.
A graph has chromatic number n + 1 if and only if it is (n + 1)-colorable and not n-colorable. Applying this characterization with n = ℓ - 1, since (C_{2ℓ - 1})ᶜ is ℓ-colorable (noting (ℓ - 1) + 1 = ℓ) and not (ℓ - 1)-colorable, its chromatic number is (ℓ - 1) + 1. Casting from ℕ∞ to ℕ and linear arithmetic simplify this to ℓ.
uses
SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable,Nat.sub_add_cancelhave := (SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable (n := ℓ - 1)).mpr ⟨by rw [Nat.sub_add_cancel (by omega)]; exact hcol, hnot⟩ rw [this] norm_cast omega
Fin.ext- Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
Fin.sub_def- Subtraction of two elements `a, b : Fin n` is defined by `((n - b) + a) % n`.
Fin.val_mk- The natural number value of `⟨m, h⟩ : Fin n` is `m`.
Fin.val_one- The natural number value of `1 : Fin n` is `1`.
Nat.add_mod_left- For natural numbers `x` and `z`, `(x + z) % x = z % x`.
Nat.mod_eq_of_lt- If `a < b` for natural numbers `a` and `b`, then `a % b = a`.
Nat.sub_add_cancel- For natural numbers with `m ≤ n`, `(n - m) + m = n`.
SimpleGraph.Coloring.mk- A proper graph coloring can be constructed from a vertex coloring map together with a proof that adjacent vertices receive different colors.
SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable- A graph has chromatic number `n + 1` if and only if it is `(n + 1)`-colorable and not `n`-colorable.
SimpleGraph.compl_adj- Two vertices are adjacent in the complement graph `Gᶜ` if and only if they are distinct and not adjacent in `G`.
SimpleGraph.cycleGraph_adj- In the cycle graph `C_{n+2}`, two vertices `u` and `v` are adjacent if and only if `u - v = 1` or `v - u = 1` in `Fin (n + 2)`.
congrArg- Applying a function to equal arguments yields equal results.
odd_antihole_chromaticNumber_aux_adj- In a cycle graph `C_N` on `N ≥ 3` vertices, any two vertices `u` and `v` whose values satisfy `u + 1 = v` are adjacent.
odd_antihole_not_colorable_of_identical_lists- The odd antihole `(C_{2ℓ - 1})ᶜ` with `ℓ ≥ 3` has no proper coloring using a fixed set of `ℓ - 1` colors.
- In Mathlib, `chromaticNumber` takes values in `ℕ∞` (the extended natural numbers with `⊤`), so concluding that the chromatic number equals `ℓ` requires a cast (`norm_cast`) and arithmetic simplification (`omega`).
- The non-colorability argument relies on `odd_antihole_not_colorable_of_identical_lists`, an established theorem in this development showing that an odd antihole cannot be colored when every vertex is given the same list of `ℓ - 1` available colors.
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.
theorem odd_antihole_chromaticNumber_aux_adj {N : ℕ} (hN : 3 ≤ N) (u v : Fin N) (h : u.val + 1 = v.val) : (SimpleGraph.cycleGraph N).Adj u v := by obtain ⟨M, rfl⟩ : ∃ M, N = M + 2 := ⟨N - 2, by omega⟩ rw [SimpleGraph.cycleGraph_adj] right rw [Fin.sub_def] ext simp only [Fin.val_mk, Fin.val_one] have hv := v.isLt rw [show M + 2 - u.val + v.val = (M + 2) + 1 by omega] rw [Nat.add_mod_left] exact Nat.mod_eq_of_lt (by omega)theorem odd_antihole_chromaticNumber (ℓ : ℕ) (hℓ : 3 ≤ ℓ) : (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.chromaticNumber = ℓ := by have hcol : (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Colorable ℓ := by refine ⟨SimpleGraph.Coloring.mk (fun u => (⟨u.val / 2, by have := u.isLt; omega⟩ : Fin ℓ)) ?_⟩ intro u v huv heq rw [SimpleGraph.compl_adj] at huv obtain ⟨hne, hnadj⟩ := huv have h2 : u.val / 2 = v.val / 2 := by simpa using congrArg Fin.val heq have hne' : u.val ≠ v.val := fun h => hne (Fin.ext h) rcases (show u.val + 1 = v.val ∨ v.val + 1 = u.val by omega) with h | h · exact hnadj (odd_antihole_chromaticNumber_aux_adj (by omega) u v h) · exact hnadj (odd_antihole_chromaticNumber_aux_adj (by omega) v u h).symm have hnot : ¬ (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Colorable (ℓ - 1) := by rintro ⟨f⟩ apply odd_antihole_not_colorable_of_identical_lists ℓ hℓ (Finset.range (ℓ - 1)) (by simp) refine ⟨fun v => (f v).val, fun v => by simp, ?_⟩ intro u v huv h exact f.valid huv (Fin.ext h) have := (SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable (n := ℓ - 1)).mpr ⟨by rw [Nat.sub_add_cancel (by omega)]; exact hcol, hnot⟩ rw [this] norm_cast omega