AFTD Auto-Formalizing Theoretical Domains

cycle_five_compl_strongly_chromatic_choosable

theoremverifiedformalization

The case ℓ = 3 of Conjecture 9: the complement of C_5 (itself a 5-cycle) is strongly 3-chromatic-choosable: χ = 3 and it is colorable from any lists of size 2 that are not all equal.

Statement

theorem cycle_five_compl_strongly_chromatic_choosable :
    IsStronglyChromaticChoosable (SimpleGraph.cycleGraph 5)ᶜ 3
Formalizes
arXiv:2610.14241 (Restricting odd antiholes in critical graphs via list coloring), remark after Conjecture 9 (the case ℓ = 3 is the well-known fact that a cycle with 2-lists is colorable unless all lists are equal); partial result for OP-216
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • IsStronglyChromaticChoosableA graph G is strongly ℓ-chromatic-choosable if χ(G) = ℓ and every (ℓ-1)-assignment L for which G is not L-colorable has all lists equal;…

The proof, explained

The proof establishes that the complement of C_5 (itself isomorphic to C_5) is strongly 3-chromatic-choosable by verifying χ = 3 and constructing a proper coloring from any 2-element lists that are not all identical. Because the lists are not all equal, two cyclically consecutive vertices have different lists, say L(p(t)) ≠ L(p(t+1)). Choosing a color a ∈ L(p(t)) absent from L(p(t+1)) enables a greedy selection of colors backwards along the cycle, where each 2-element list contains a color different from the previous one. The cycle closes without conflict because the final vertex p(t+1) cannot pick a, which is not in its list.

  1. Adjacency in the complement of C_5 corresponds to being consecutive modulo 5 under the permutation q = [0, 3, 1, 4, 2]. automation

    The graph complement of C_5 has edges between vertices at distance 2 in C_5. Permuting vertices via q maps this complement graph isomorphically to the standard cycle graph, so two vertices u, v are adjacent if and only if q(v) = q(u) ± 1. This equivalence is verified for all pairs by exhaustive evaluation (`decide`).

    lines 1–6

    theorem cycle_five_compl_adj_iff (u v : Fin 5) :
        (SimpleGraph.cycleGraph 5)ᶜ.Adj u v ↔
          (![0, 3, 1, 4, 2] : Fin 5 → Fin 5) v = (![0, 3, 1, 4, 2] : Fin 5 → Fin 5) u + 1 ∨
          (![0, 3, 1, 4, 2] : Fin 5 → Fin 5) u = (![0, 3, 1, 4, 2] : Fin 5 → Fin 5) v + 1 := by
      revert u v; decide
    
  2. The complement of C_5 has no proper 2-coloring. automation

    Because the complement of C_5 is an odd cycle (a 5-cycle), it is not bipartite and cannot be 2-colored. Lean checks all 2^5 = 32 possible assignments of two colors to the five vertices by exhaustive search (`decide`), confirming that each assignment gives adjacent vertices the same color.

    lines 7–10

    theorem cycle_five_compl_not_two_colorable :
        ∀ f : Fin 5 → Fin 2, ∃ u v, (SimpleGraph.cycleGraph 5)ᶜ.Adj u v ∧ f u = f v := by
      decide
    
  3. Every 2-element set of natural numbers contains an element distinct from any specified number b.

    Applying Finset.card_eq_two.mp to the hypothesis |s| = 2 gives s = {x, y} with x ≠ y. A case distinction on whether x = b provides the witness: if x = b, then y ≠ b because x ≠ y; if x ≠ b, then x itself is different from b.

    lines 11–18

    uses Finset.card_eq_two.mp

    theorem finset_card_two_exists_ne (s : Finset ℕ) (hs : s.card = 2) (b : ℕ) : ∃ y ∈ s, y ≠ b := by
      obtain ⟨x, y, hxy, rfl⟩ := Finset.card_eq_two.mp hs
      by_cases hx : x = b
      · exact ⟨y, by simp, fun h => hxy (hx.trans h.symm)⟩
      · exact ⟨x, by simp, hx⟩
    
    theorem cycle_five_compl_strongly_chromatic_choosable :
        IsStronglyChromaticChoosable (SimpleGraph.cycleGraph 5)ᶜ 3 := by
  4. We define mutual inverse permutations p and q on Fin 5 that identify the complement graph with the standard 5-cycle ordering.

    The complement of C_5 is isomorphic to C_5 itself. We define p = [0, 2, 4, 1, 3] to traverse the vertices in cyclic order along the complement graph, and q = [0, 3, 1, 4, 2] as its inverse permutation. The identity p(q(u)) = u for all u is verified by finite evaluation (`decide`).

    lines 19–22

      classical
      set p : Fin 5 → Fin 5 := ![0, 2, 4, 1, 3] with hp
      set q : Fin 5 → Fin 5 := ![0, 3, 1, 4, 2] with hq
      have hpq : ∀ u, p (q u) = u := by decide
  5. The chromatic number of the complement of C_5 is 3.

    We prove that the complement of C_5 is 3-colorable but not 2-colorable. A valid 3-coloring is given explicitly by u ↦ ⌊u / 2⌋ ∈ Fin 3 using SimpleGraph.Coloring.mk, checked by finite evaluation (`decide`). The lemma cycle_five_compl_not_two_colorable shows that any 2-coloring assigns the same color to some adjacent pair, so no 2-coloring exists. SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable then establishes that the chromatic number is 2 + 1 = 3.

    lines 23–35

    uses SimpleGraph.Coloring.mk, cycle_five_compl_not_two_colorable, SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable

      refine ⟨?_, ?_⟩
      · have h3 : (SimpleGraph.cycleGraph 5)ᶜ.Colorable 3 :=
          ⟨SimpleGraph.Coloring.mk (fun u => (⟨u.val / 2, by omega⟩ : Fin 3)) (by
            intro u v huv
            revert huv
            revert u v
            decide)⟩
        have h2 : ¬ (SimpleGraph.cycleGraph 5)ᶜ.Colorable 2 := by
          rintro ⟨f⟩
          obtain ⟨u, v, huv, hf⟩ := cycle_five_compl_not_two_colorable f
          exact f.valid huv hf
        have := (SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable (n := 2)).mpr ⟨h3, h2⟩
        exact this.trans (by norm_num)
  6. We introduce a list assignment L of 2-element lists that are not all identical.

    We fix a list assignment L such that each list L(v) has size 3 - 1 = 2 (recorded as hL2), and assume the hypothesis hne that there exist vertices u, v with L(u) ≠ L(v).

    lines 36–38

      · intro L hL hne
        have hL2 : ∀ v, (L v).card = 2 := hL
        -- a consecutive pair (in the cycle order p of the complement) with different lists
  7. There exists a vertex along the cycle whose list differs from that of the next vertex in cycle order.

    We argue by contradiction: if every consecutive pair along the cycle had identical lists (L(p(t)) = L(p(t+1)) for all t), then by transitivity around the 5-cycle, every list L(p(s)) would equal L(p(0)). Since p(q(u)) = u, every vertex u would have the identical list L(p(0)), contradicting the assumption hne that not all lists are equal.

    lines 39–53

        have hcons : ∃ t : Fin 5, L (p t) ≠ L (p (t + 1)) := by
          by_contra h
          push Not at h
          have hall : ∀ s : Fin 5, L (p s) = L (p 0) := by
            intro s
            have e1 := h 0; have e2 := h 1; have e3 := h 2; have e4 := h 3
            fin_cases s
            · rfl
            · exact e1.symm
            · exact (e1.trans e2).symm
            · exact (e1.trans (e2.trans e3)).symm
            · exact (e1.trans (e2.trans (e3.trans e4))).symm
          obtain ⟨u, v, huv⟩ := hne
          apply huv
          rw [← hpq u, ← hpq v, hall (q u), hall (q v)]
  8. There is a color a in the list of p(t) that is not in the list of the next vertex p(t+1).

    Since L(p(t)) and L(p(t+1)) are distinct sets of the same cardinality 2, L(p(t)) cannot be a subset of L(p(t+1)), as Finset.eq_of_subset_of_card_le would then force them to be equal. Hence there exists an element a ∈ L(p(t)) with a ∉ L(p(t+1)).

    lines 54–58

    uses Finset.eq_of_subset_of_card_le

        obtain ⟨t, ht⟩ := hcons
        obtain ⟨a, haA, haB⟩ : ∃ a ∈ L (p t), a ∉ L (p (t + 1)) := by
          by_contra h
          push Not at h
          exact ht (Finset.eq_of_subset_of_card_le h (by rw [hL2, hL2]))
  9. We greedily choose colors along the cycle in reverse order, ensuring adjacent colors differ and the final color avoids a.

    With color a fixed at p(t), we walk backwards along the cycle. Since every list has size 2, finset_card_two_exists_ne allows us to pick c1 ∈ L(p(t-1)) with c1 ≠ a, then c2 ∈ L(p(t-2)) with c2 ≠ c1, then c3 ∈ L(p(t-3)) with c3 ≠ c2, and finally c4 ∈ L(p(t-4)) with c4 ≠ c3. In Fin 5, t - 4 = t + 1, so p(t-4) is the forward neighbour p(t+1). Since c4 ∈ L(p(t+1)) and a ∉ L(p(t+1)), we automatically obtain c4 ≠ a.

    lines 59–67

    uses finset_card_two_exists_ne

        obtain ⟨c1, hc1, hc1a⟩ := finset_card_two_exists_ne (L (p (t - 1))) (hL2 _) a
        obtain ⟨c2, hc2, hc21⟩ := finset_card_two_exists_ne (L (p (t - 2))) (hL2 _) c1
        obtain ⟨c3, hc3, hc32⟩ := finset_card_two_exists_ne (L (p (t - 3))) (hL2 _) c2
        obtain ⟨c4, hc4, hc43⟩ := finset_card_two_exists_ne (L (p (t - 4))) (hL2 _) c3
        have ht4 : t - 4 = t + 1 := by
          have key : ∀ x : Fin 5, x - 4 = x + 1 := by decide
          exact key t
        have hc4a : c4 ≠ a := by
          intro h; rw [ht4] at hc4; exact haB (h ▸ hc4)
  10. The color sequence col = [a, c1, c2, c3, c4] selects valid colors from the lists and has distinct cyclically adjacent entries.

    We pack the chosen colors into the sequence col. For each of the five cycle indices k ∈ Fin 5, case analysis (`fin_cases`) confirms that col(k) belongs to L(p(t-k)) by construction (hcolmem), and cyclically adjacent entries are distinct: c1 ≠ a, c2 ≠ c1, c3 ≠ c2, c4 ≠ c3, and a ≠ c4 (hcolne).

    lines 68–84

        set col : Fin 5 → ℕ := ![a, c1, c2, c3, c4] with hcol
        have hcolmem : ∀ k : Fin 5, col k ∈ L (p (t - k)) := by
          intro k
          fin_cases k
          · simpa [hcol] using haA
          · simpa [hcol] using hc1
          · simpa [hcol] using hc2
          · simpa [hcol] using hc3
          · simpa [hcol] using hc4
        have hcolne : ∀ k : Fin 5, col (k + 1) ≠ col k := by
          intro k
          fin_cases k
          · simpa [hcol] using hc1a
          · simpa [hcol] using hc21
          · simpa [hcol] using hc32
          · simpa [hcol] using hc43
          · simpa [hcol] using hc4a.symm
  11. The assigned color col(t - q(u)) belongs to L(u) for every vertex u.

    For any vertex u, hcolmem shows col(t - q(u)) ∈ L(p(t - (t - q(u)))). By sub_sub_cancel, t - (t - q(u)) simplifies to q(u), and p(q(u)) = u by hpq, so this is L(u).

    lines 85–88

    uses sub_sub_cancel

        refine ⟨fun u => col (t - q u), ?_, ?_⟩
        · intro u
          have := hcolmem (t - q u)
          rwa [sub_sub_cancel, hpq] at this
  12. The coloring is proper: adjacent vertices in the complement graph receive distinct colors.

    If u and v are adjacent in the complement of C_5, cycle_five_compl_adj_iff states that their cycle positions q(u) and q(v) differ by 1 modulo 5. In either case, the indices t - q(u) and t - q(v) are cyclically adjacent in Fin 5 (verified with `abel`), so hcolne ensures that their colors col(t - q(u)) and col(t - q(v)) are distinct.

    lines 89–100

    uses cycle_five_compl_adj_iff

        · intro u v huv
          have hadj := (cycle_five_compl_adj_iff u v).mp huv
          rw [← hq] at hadj
          rcases hadj with h | h
          · have e : t - q v + 1 = t - q u := by rw [h]; abel
            have := hcolne (t - q v)
            rw [e] at this
            exact this
          · have e : t - q u + 1 = t - q v := by rw [h]; abel
            have := hcolne (t - q u)
            rw [e] at this
            exact fun h' => this h'.symm
Finset.card_eq_two.mp
A finite set has cardinality 2 if and only if it consists of two distinct elements.
SimpleGraph.Coloring.mk
Constructs a proper vertex coloring of a graph from a color assignment function and a proof that adjacent vertices receive different colors.
cycle_five_compl_not_two_colorable
For every 2-coloring of the vertices of the complement of C_5, there exists a pair of adjacent vertices with the same color.
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.
Finset.eq_of_subset_of_card_le
If s and t are finite sets with s ⊆ t and |t| ≤ |s|, then s = t.
finset_card_two_exists_ne
In any 2-element set of natural numbers, for every element b, there exists an element of the set not equal to b.
sub_sub_cancel
In an additive group, a - (a - b) = b.
cycle_five_compl_adj_iff
Two vertices u, v ∈ Fin 5 are adjacent in the complement of C_5 if and only if their cycle positions under the permutation q = [0, 3, 1, 4, 2] differ by 1 modulo 5.

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 cycle_five_compl_adj_iff (u v : Fin 5) :    (SimpleGraph.cycleGraph 5)ᶜ.Adj u v ↔      (![0, 3, 1, 4, 2] : Fin 5 → Fin 5) v = (![0, 3, 1, 4, 2] : Fin 5 → Fin 5) u + 1 ∨      (![0, 3, 1, 4, 2] : Fin 5 → Fin 5) u = (![0, 3, 1, 4, 2] : Fin 5 → Fin 5) v + 1 := by  revert u v; decidetheorem cycle_five_compl_not_two_colorable :    ∀ f : Fin 5 → Fin 2, ∃ u v, (SimpleGraph.cycleGraph 5)ᶜ.Adj u v ∧ f u = f v := by  decidetheorem finset_card_two_exists_ne (s : Finset ℕ) (hs : s.card = 2) (b : ℕ) : ∃ y ∈ s, y ≠ b := by  obtain ⟨x, y, hxy, rfl⟩ := Finset.card_eq_two.mp hs  by_cases hx : x = b  · exact ⟨y, by simp, fun h => hxy (hx.trans h.symm)⟩  · exact ⟨x, by simp, hx⟩theorem cycle_five_compl_strongly_chromatic_choosable :    IsStronglyChromaticChoosable (SimpleGraph.cycleGraph 5)ᶜ 3 := by  classical  set p : Fin 5 → Fin 5 := ![0, 2, 4, 1, 3] with hp  set q : Fin 5 → Fin 5 := ![0, 3, 1, 4, 2] with hq  have hpq : ∀ u, p (q u) = u := by decide  refine ⟨?_, ?_⟩  · have h3 : (SimpleGraph.cycleGraph 5)ᶜ.Colorable 3 :=      ⟨SimpleGraph.Coloring.mk (fun u => (⟨u.val / 2, by omega⟩ : Fin 3)) (by        intro u v huv        revert huv        revert u v        decide)⟩    have h2 : ¬ (SimpleGraph.cycleGraph 5)ᶜ.Colorable 2 := by      rintro ⟨f⟩      obtain ⟨u, v, huv, hf⟩ := cycle_five_compl_not_two_colorable f      exact f.valid huv hf    have := (SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable (n := 2)).mpr ⟨h3, h2⟩    exact this.trans (by norm_num)  · intro L hL hne    have hL2 : ∀ v, (L v).card = 2 := hL    -- a consecutive pair (in the cycle order p of the complement) with different lists    have hcons : ∃ t : Fin 5, L (p t) ≠ L (p (t + 1)) := by      by_contra h      push Not at h      have hall : ∀ s : Fin 5, L (p s) = L (p 0) := by        intro s        have e1 := h 0; have e2 := h 1; have e3 := h 2; have e4 := h 3        fin_cases s        · rfl        · exact e1.symm        · exact (e1.trans e2).symm        · exact (e1.trans (e2.trans e3)).symm        · exact (e1.trans (e2.trans (e3.trans e4))).symm      obtain ⟨u, v, huv⟩ := hne      apply huv      rw [← hpq u, ← hpq v, hall (q u), hall (q v)]    obtain ⟨t, ht⟩ := hcons    obtain ⟨a, haA, haB⟩ : ∃ a ∈ L (p t), a ∉ L (p (t + 1)) := by      by_contra h      push Not at h      exact ht (Finset.eq_of_subset_of_card_le h (by rw [hL2, hL2]))    obtain ⟨c1, hc1, hc1a⟩ := finset_card_two_exists_ne (L (p (t - 1))) (hL2 _) a    obtain ⟨c2, hc2, hc21⟩ := finset_card_two_exists_ne (L (p (t - 2))) (hL2 _) c1    obtain ⟨c3, hc3, hc32⟩ := finset_card_two_exists_ne (L (p (t - 3))) (hL2 _) c2    obtain ⟨c4, hc4, hc43⟩ := finset_card_two_exists_ne (L (p (t - 4))) (hL2 _) c3    have ht4 : t - 4 = t + 1 := by      have key : ∀ x : Fin 5, x - 4 = x + 1 := by decide      exact key t    have hc4a : c4 ≠ a := by      intro h; rw [ht4] at hc4; exact haB (h ▸ hc4)    set col : Fin 5 → ℕ := ![a, c1, c2, c3, c4] with hcol    have hcolmem : ∀ k : Fin 5, col k ∈ L (p (t - k)) := by      intro k      fin_cases k      · simpa [hcol] using haA      · simpa [hcol] using hc1      · simpa [hcol] using hc2      · simpa [hcol] using hc3      · simpa [hcol] using hc4    have hcolne : ∀ k : Fin 5, col (k + 1) ≠ col k := by      intro k      fin_cases k      · simpa [hcol] using hc1a      · simpa [hcol] using hc21      · simpa [hcol] using hc32      · simpa [hcol] using hc43      · simpa [hcol] using hc4a.symm    refine ⟨fun u => col (t - q u), ?_, ?_⟩    · intro u      have := hcolmem (t - q u)      rwa [sub_sub_cancel, hpq] at this    · intro u v huv      have hadj := (cycle_five_compl_adj_iff u v).mp huv      rw [← hq] at hadj      rcases hadj with h | h      · have e : t - q v + 1 = t - q u := by rw [h]; abel        have := hcolne (t - q v)        rw [e] at this        exact this      · have e : t - q u + 1 = t - q v := by rw [h]; abel        have := hcolne (t - q u)        rw [e] at this        exact fun h' => this h'.symm
See it in the graphDiscuss this resultChallenge it