cycle_five_compl_strongly_chromatic_choosable
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.
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`).
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
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.
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
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.
uses
Finset.card_eq_two.mptheorem 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
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`).
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
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.
uses
SimpleGraph.Coloring.mk,cycle_five_compl_not_two_colorable,SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorablerefine ⟨?_, ?_⟩ · 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)
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).
· 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
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.
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)]
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)).
uses
Finset.eq_of_subset_of_card_leobtain ⟨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]))
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.
uses
finset_card_two_exists_neobtain ⟨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)
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).
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
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).
uses
sub_sub_cancelrefine ⟨fun u => col (t - q u), ?_, ?_⟩ · intro u have := hcolmem (t - q u) rwa [sub_sub_cancel, hpq] at this
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.
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.
- The 5-cycle complement's adjacency relation, 3-colorability, and non-2-colorability are all verified by exhaustive finite search using `decide`.
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 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