AFTD Auto-Formalizing Theoretical Domains

odd_antihole_chromaticNumber

theoremverified

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

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.

  1. 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.

    lines 3–12

    uses SimpleGraph.cycleGraph_adj, Fin.sub_def, Fin.val_mk, Fin.val_one, Nat.add_mod_left, Nat.mod_eq_of_lt

      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)
  2. 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.

    lines 16–25

    uses SimpleGraph.Coloring.mk, SimpleGraph.compl_adj, congrArg, Fin.ext, odd_antihole_chromaticNumber_aux_adj

      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
  3. 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.

    lines 26–31

    uses odd_antihole_not_colorable_of_identical_lists, Fin.ext

      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)
  4. 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 ℓ.

    lines 32–36

    uses SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable, Nat.sub_add_cancel

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it