cycle_three_proportionally_three_choosable
The triangle cycle C_3 is proportionally 3-choosable: for every finite color palette α and every assignment L of 3 colors to each vertex, there exists a proper coloring f of C_3 with f(v) ∈ L(v) for all v such that for every color c : α, the number of vertices colored c is either ⌊η_L(c)/3⌋ or ⌈η_L(c)/3⌉, where η_L(c) is the number of vertices whose list contains c.
Statement
theorem cycle_three_proportionally_three_choosable : ∀ (α : Type) [Fintype α] [DecidableEq α] (L : Fin 3 → Finset α), (∀ v, (L v).card = 3) → ∃ f : (SimpleGraph.cycleGraph 3).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 = η / 3 ∨ uses = η ⌈/⌉ 3
- Source
- arXiv:2610.33914 Section 2 (special case n = 3 of OP-593)
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any finite type α with decidable equality, and for any list assignment L : Fin 3 → Finset α assigning to each vertex of Fin 3 a set of colors of cardinality 3 (i.e., ∀ v : Fin 3, (L v).card = 3), there exists a proper coloring f of the 3-cycle graph (SimpleGraph.cycleGraph 3) with colors in α such that: 1. For every vertex v : Fin 3, f v ∈ L v (f is a list coloring from L); 2. For every color c : α, the number of vertices colored c by f (i.e., the cardinality of {v : Fin 3 | f v = c}) is equal to either ⌊η / 3⌋ (natural division) or ⌈η / 3⌉ (natural ceiling division), where η is the number of vertices v : Fin 3 such that c ∈ L v (the cardinality of {v : Fin 3 | c ∈ L v}).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To prove that the cycle C_3 is proportionally 3-choosable, it suffices to find distinct representatives x ∈ L(0), y ∈ L(1), and z ∈ L(2) that cover the triple intersection U = L(0) ∩ L(1) ∩ L(2). Because C_3 is the complete graph K_3, any distinct triple (x, y, z) yields a proper coloring where each color is used at most once, which immediately satisfies the proportional rounding bounds for any color appearing in at most two lists. The only tight condition is for colors present in all three lists (η_L(c) = 3), which must be used at least ⌈3/3⌉ = 1 time; greedy selection from the lists ensures that all elements of U are covered by {x, y, z} without exceeding |U| ≤ 3.
A predicate on Fin 3 holds for all three elements if and only if the filtered universe has cardinality 3.
For the forward implication, if the filtered set has cardinality 3, its cardinality equals that of Fin 3, so it is the entire universe by Finset.eq_univ_of_card; hence the predicate holds for 0, 1, and 2. Conversely, if the predicate holds on 0, 1, and 2, then by exhaustive case analysis on Fin 3 every element satisfies it, so the filtered set is all of Fin 3 and has cardinality 3.
uses
Finset.eq_univ_of_cardconstructor · intro h have hs : Finset.univ.filter p = Finset.univ := by apply Finset.eq_univ_of_card simpa using h have hall : ∀ v : Fin 3, p v := by intro v have hv : v ∈ Finset.univ.filter p := by rw [hs] simp simpa using hv exact ⟨hall 0, hall 1, hall 2⟩ · rintro ⟨h0, h1, h2⟩ have hs : Finset.univ.filter p = Finset.univ := by ext v fin_cases v <;> simp [h0, h1, h2] rw [hs] simp
The triple intersection U = A ∩ B ∩ C is a subset of A, B, and C, and has cardinality at most 3.
By definition of set intersection, any element of U belongs to A, B, and C via Finset.mem_inter. Since U ⊆ A and |A| = 3, monotonicity of cardinality (Finset.card_le_card) gives |U| ≤ 3.
uses
Finset.mem_inter,Finset.card_le_cardlet U : Finset α := A ∩ B ∩ C have hUsubA : U ⊆ A := by intro a ha simp only [U, Finset.mem_inter] at ha exact ha.1.1 have hUsubB : U ⊆ B := by intro a ha simp only [U, Finset.mem_inter] at ha exact ha.1.2 have hUsubC : U ⊆ C := by intro a ha simp only [U, Finset.mem_inter] at ha exact ha.2 have hUcard : U.card ≤ 3 := by calc U.card ≤ A.card := Finset.card_le_card hUsubA _ = 3 := hA
There exists an element x ∈ A such that if U is nonempty, then x ∈ U.
We split on whether U is nonempty. If it is, we choose x to be an element of U (which also belongs to A since U ⊆ A). If U is empty, since |A| = 3 > 0, A is nonempty by Finset.card_pos.mp, so we choose any x ∈ A. In either case, x ∈ A and U ≠ ∅ → x ∈ U.
uses
Finset.card_pos.mphave hx_exists : ∃ x, x ∈ A ∧ (U.Nonempty → x ∈ U) := by by_cases hUne : U.Nonempty · obtain ⟨x, hxU⟩ := hUne.exists_mem exact ⟨x, hUsubA hxU, fun _ => hxU⟩ · have hApos : 0 < A.card := by omega obtain ⟨x, hxA⟩ := Finset.card_pos.mp hApos exact ⟨x, hxA, fun h => (hUne h).elim⟩ obtain ⟨x, hxA, hxUcond⟩ := hx_exists
There exists an element y ∈ B distinct from x such that if U \ {x} is nonempty, then y ∈ U \ {x}.
By Finset.le_card_sdiff and Finset.card_singleton, |B \ {x}| ≥ |B| - 1 = 2 > 0, so B \ {x} is nonempty by Finset.card_pos.mp. If U \ {x} is nonempty, we pick y ∈ U \ {x}, which lies in B and is distinct from x by Finset.mem_of_mem_erase and Finset.ne_of_mem_erase. If U \ {x} is empty, we pick y from the nonempty set B \ {x} using Finset.mem_sdiff.
uses
Finset.le_card_sdiff,Finset.card_singleton,Finset.card_pos.mp,Finset.mem_of_mem_erase,Finset.ne_of_mem_erase,Finset.mem_sdiffhave hy_base : (B \ {x}).Nonempty := by have hle := Finset.le_card_sdiff ({x} : Finset α) B rw [Finset.card_singleton, hB] at hle have hpos : 0 < (B \ {x}).card := by omega exact Finset.card_pos.mp hpos have hy_exists : ∃ y, y ∈ B ∧ y ≠ x ∧ ((U.erase x).Nonempty → y ∈ U.erase x) := by by_cases hUx : (U.erase x).Nonempty · obtain ⟨y, hyUx⟩ := hUx.exists_mem exact ⟨y, hUsubB (Finset.mem_of_mem_erase hyUx), Finset.ne_of_mem_erase hyUx, fun _ => hyUx⟩ · obtain ⟨y, hyBdiff⟩ := hy_base rw [Finset.mem_sdiff] at hyBdiff exact ⟨y, hyBdiff.1, by simpa using hyBdiff.2, fun h => (hUx h).elim⟩ obtain ⟨y, hyB, hyx, hyUcond⟩ := hy_exists have hxy : x ≠ y := hyx.symm
There exists an element z ∈ C distinct from both x and y such that if U \ {x, y} is nonempty, then z ∈ U \ {x, y}, and the set {x, y, z} has cardinality 3.
Since x ≠ y, {x, y} has cardinality 2 by Finset.card_pair. By Finset.le_card_sdiff, |C \ {x, y}| ≥ 3 - 2 = 1 > 0, so C \ {x, y} is nonempty by Finset.card_pos.mp. If U \ {x, y} is nonempty, we select z ∈ U \ {x, y}; otherwise we pick z ∈ C \ {x, y} using Finset.mem_sdiff. In either case z ∈ C, z ≠ x, and z ≠ y. Because x, y, z are pairwise distinct, |{x, y, z}| = 3.
uses
Finset.le_card_sdiff,Finset.card_pair,Finset.card_pos.mp,Finset.mem_sdiffhave hz_base : (C \ ({x, y} : Finset α)).Nonempty := by have hle := Finset.le_card_sdiff ({x, y} : Finset α) C rw [Finset.card_pair hxy, hC] at hle have hpos : 0 < (C \ ({x, y} : Finset α)).card := by omega exact Finset.card_pos.mp hpos have hz_exists : ∃ z, z ∈ C ∧ z ≠ x ∧ z ≠ y ∧ ((U \ ({x, y} : Finset α)).Nonempty → z ∈ U \ ({x, y} : Finset α)) := by by_cases hUxy : (U \ ({x, y} : Finset α)).Nonempty · obtain ⟨z, hzUxy⟩ := hUxy.exists_mem rw [Finset.mem_sdiff] at hzUxy have hzx : z ≠ x := by intro hzx exact hzUxy.2 (by simp [hzx]) have hzy : z ≠ y := by intro hzy exact hzUxy.2 (by simp [hzy]) exact ⟨z, hUsubC hzUxy.1, hzx, hzy, fun _ => by rw [Finset.mem_sdiff] exact hzUxy⟩ · obtain ⟨z, hzCdiff⟩ := hz_base rw [Finset.mem_sdiff] at hzCdiff have hzx : z ≠ x := by intro hzx exact hzCdiff.2 (by simp [hzx]) have hzy : z ≠ y := by intro hzy exact hzCdiff.2 (by simp [hzy]) exact ⟨z, hzCdiff.1, hzx, hzy, fun h => (hUxy h).elim⟩ obtain ⟨z, hzC, hzx, hzy, hzUcond⟩ := hz_exists have hxz : x ≠ z := hzx.symm have hyz : y ≠ z := hzy.symm have hcard3 : ({x, y, z} : Finset α).card = 3 := by exact Finset.card_eq_three.mpr ⟨x, y, z, hxy, hxz, hyz, rfl⟩
The chosen elements x, y, z cover the intersection U = A ∩ B ∩ C, completing the proof of the distinct representatives lemma.
Let c ∈ U. If c = x or c = y, the claim is immediate. If c ≠ x and c ≠ y, we show c = z by contradiction: suppose c ≠ z. Since c ∈ U and c ≠ x, U \ {x} was nonempty, so by construction y ∈ U using Finset.mem_of_mem_erase. Similarly, since c ∉ {x, y}, U \ {x, y} was nonempty, so z ∈ U. Since U was nonempty, x ∈ U as well. Thus {x, y, z} ⊆ U. But c ∈ U and c ∉ {x, y, z}, so {x, y, z} is a strict subset of U by Finset.ssubset_iff_of_subset. By Finset.card_lt_card, this forces |U| > |{x, y, z}| = 3, contradicting |U| ≤ 3.
uses
Finset.mem_inter,Finset.mem_of_mem_erase,Finset.ssubset_iff_of_subset,Finset.card_lt_cardrefine ⟨x, y, z, hxA, hyB, hzC, hxy, hxz, hyz, ?_⟩ intro c hcA hcB hcC have hcU : c ∈ U := by simp only [U, Finset.mem_inter] exact ⟨⟨hcA, hcB⟩, hcC⟩ by_cases hcx : c = x · exact Or.inl hcx · by_cases hcy : c = y · exact Or.inr (Or.inl hcy) · right; right by_contra hcz have hUxne : (U.erase x).Nonempty := ⟨c, Finset.mem_erase.mpr ⟨hcx, hcU⟩⟩ have hyUx := hyUcond hUxne have hyU : y ∈ U := Finset.mem_of_mem_erase hyUx have hcnotxy : c ∉ ({x, y} : Finset α) := by simp [hcx, hcy] have hUxyne : (U \ ({x, y} : Finset α)).Nonempty := ⟨c, Finset.mem_sdiff.mpr ⟨hcU, hcnotxy⟩⟩ have hzUxy := hzUcond hUxyne have hzU : z ∈ U := (Finset.mem_sdiff.mp hzUxy).1 have hxU : x ∈ U := hxUcond ⟨c, hcU⟩ have hsub : ({x, y, z} : Finset α) ⊆ U := by intro a ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl · exact hxU · exact hyU · exact hzU have hcnot : c ∉ ({x, y, z} : Finset α) := by simp [hcx, hcy, hcz] have hssub : ({x, y, z} : Finset α) ⊂ U := (Finset.ssubset_iff_of_subset hsub).mpr ⟨c, hcU, hcnot⟩ have hlt := Finset.card_lt_card hssub rw [hcard3] at hlt omega
Assigning pairwise distinct colors x, y, z to the vertices of the triangle graph C_3 produces a proper coloring.
The cycle graph C_3 is isomorphic to the complete graph on 3 vertices by SimpleGraph.cycleGraph_three_eq_top. Since x, y, z are pairwise distinct, any two adjacent vertices are assigned distinct colors by Ne.symm, yielding a valid vertex coloring.
uses
SimpleGraph.cycleGraph_three_eq_top,Ne.symmrefine ⟨SimpleGraph.Coloring.mk (![x, y, z] : Fin 3 → α) ?_, ?_, ?_, ?_⟩ · intro v w h rw [SimpleGraph.cycleGraph_three_eq_top] at h fin_cases v <;> fin_cases w <;> simp_all [Ne.symm] · rfl · rfl · rfl
For any natural number n ∈ {1, 2, 3}, the ceiling division n ⌈/⌉ 3 equals 1.
We rewrite ceiling division using Nat.ceilDiv_eq_add_pred_div into ⌊(n + 2) / 3⌋. The claim is then verified for n ∈ {1, 2, 3} by exhaustive case analysis and simple arithmetic.
uses
Nat.ceilDiv_eq_add_pred_divrw [Nat.ceilDiv_eq_add_pred_div] interval_cases n <;> norm_num
There exists a proper coloring f of C_3 such that f(v) ∈ L(v) for each vertex v ∈ Fin 3.
Applying cycle_three_proportionally_three_choosable_exists_distinct to lists L(0), L(1), L(2) of size 3 yields distinct colors x ∈ L(0), y ∈ L(1), z ∈ L(2) covering L(0) ∩ L(1) ∩ L(2). Then cycle_three_proportionally_three_choosable_cycle_three_coloring_of_distinct provides a proper coloring f with f(0) = x, f(1) = y, and f(2) = z. Evaluating f at each vertex confirms f(v) ∈ L(v) for all v.
uses
cycle_three_proportionally_three_choosable_exists_distinct,cycle_three_proportionally_three_choosable_cycle_three_coloring_of_distinctintro α _ _ L hL obtain ⟨x, y, z, hxA, hyB, hzC, hxy, hxz, hyz, hcover⟩ := cycle_three_proportionally_three_choosable_exists_distinct (L 0) (L 1) (L 2) (hL 0) (hL 1) (hL 2) obtain ⟨f, hf0, hf1, hf2⟩ := cycle_three_proportionally_three_choosable_cycle_three_coloring_of_distinct x y z hxy hxz hyz refine ⟨f, ?_, ?_⟩ · intro v fin_cases v · simpa [hf0] using hxA · simpa [hf1] using hyB · simpa [hf2] using hzC
For any color c, the list frequency satisfies η ≤ 3, η = 3 implies c ∈ L(0) ∩ L(1) ∩ L(2), and each chosen color x, y, z is used by f exactly once.
Since there are only 3 vertices in Fin 3, η ≤ 3 by Finset.card_le_univ. If η = 3, all three vertices contain c in their list by cycle_three_proportionally_three_choosable_fin_three_filter_card_eq_three_iff. Since f assigns distinct values x, y, z to vertices 0, 1, 2, the set of vertices colored x is {0}, colored y is {1}, and colored z is {2} (using Ne.symm), each of cardinality 1.
uses
Finset.card_le_univ,cycle_three_proportionally_three_choosable_fin_three_filter_card_eq_three_iff,Ne.symm· intro c dsimp only set η : ℕ := (Finset.univ.filter (fun v : Fin 3 => c ∈ L v)).card with hηdef set uses : ℕ := (Finset.univ.filter (fun v : Fin 3 => f v = c)).card with husesdef change uses = η / 3 ∨ uses = η ⌈/⌉ 3 have hηle : η ≤ 3 := by rw [hηdef] simpa using Finset.card_le_univ (Finset.univ.filter (fun v : Fin 3 => c ∈ L v)) have hη_three_imp : η = 3 → c ∈ L 0 ∧ c ∈ L 1 ∧ c ∈ L 2 := by intro hη3 have hcard : (Finset.univ.filter (fun v : Fin 3 => c ∈ L v)).card = 3 := by rw [hηdef] at hη3 exact hη3 exact (cycle_three_proportionally_three_choosable_fin_three_filter_card_eq_three_iff (p := fun v : Fin 3 => c ∈ L v)).mp hcard have huse_x : (Finset.univ.filter (fun v : Fin 3 => f v = x)).card = 1 := by rw [show (Finset.univ.filter (fun v : Fin 3 => f v = x)) = {0} by ext v fin_cases v <;> simp [hf0, hf1, hf2, Ne.symm hxy, Ne.symm hxz]] simp have huse_y : (Finset.univ.filter (fun v : Fin 3 => f v = y)).card = 1 := by rw [show (Finset.univ.filter (fun v : Fin 3 => f v = y)) = {1} by ext v fin_cases v <;> simp [hf0, hf1, hf2, hxy, Ne.symm hyz]] simp have huse_z : (Finset.univ.filter (fun v : Fin 3 => f v = z)).card = 1 := by rw [show (Finset.univ.filter (fun v : Fin 3 => f v = z)) = {2} by ext v fin_cases v <;> simp [hf0, hf1, hf2, hxz, hyz]] simp
If c ∈ {x, y, z}, then the number of vertices colored c equals ⌈η / 3⌉.
If c = x, c = y, or c = z, then c is used exactly once (uses = 1). Since c belongs to at least one list (x ∈ L(0), y ∈ L(1), or z ∈ L(2)), its list frequency satisfies η > 0 by Finset.card_pos.mpr. Since 0 < η ≤ 3, cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one gives η ⌈/⌉ 3 = 1 = uses, satisfying the proportional ceiling bound.
uses
Finset.card_pos.mpr,cycle_three_proportionally_three_choosable_ceilDiv_three_eq_oneby_cases hcx : c = x · subst c have huse : uses = 1 := by rw [husesdef] exact huse_x have hηpos : 0 < η := by rw [hηdef] apply Finset.card_pos.mpr exact ⟨0, by simp [hxA]⟩ have hceil : η ⌈/⌉ 3 = 1 := cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one hηpos hηle right rw [huse, hceil] · by_cases hcy : c = y · subst c have huse : uses = 1 := by rw [husesdef] exact huse_y have hηpos : 0 < η := by rw [hηdef] apply Finset.card_pos.mpr exact ⟨1, by simp [hyB]⟩ have hceil : η ⌈/⌉ 3 = 1 := cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one hηpos hηle right rw [huse, hceil] · by_cases hcz : c = z · subst c have huse : uses = 1 := by rw [husesdef] exact huse_z have hηpos : 0 < η := by rw [hηdef] apply Finset.card_pos.mpr exact ⟨2, by simp [hzC]⟩ have hceil : η ⌈/⌉ 3 = 1 := cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one hηpos hηle right rw [huse, hceil]
If c ∉ {x, y, z}, then the number of vertices colored c equals ⌊η / 3⌋, completing the proof.
Since c ≠ x, y, z, no vertex is colored c, so uses = 0 by Finset.card_eq_zero, Finset.filter_false_of_mem, and Ne.symm. If η ≥ 3, then η = 3, which would imply c ∈ L(0) ∩ L(1) ∩ L(2); but by the covering property of x, y, z, this forces c ∈ {x, y, z}, a contradiction. Thus η < 3, which implies η / 3 = 0 by Nat.div_eq_of_lt. Therefore uses = ⌊η / 3⌋.
uses
Finset.card_eq_zero,Finset.filter_false_of_mem,Nat.div_eq_of_lt,Ne.symm· have huse : uses = 0 := by rw [husesdef, Finset.card_eq_zero] apply Finset.filter_false_of_mem intro v _ fin_cases v <;> simp [hf0, hf1, hf2, Ne.symm hcx, Ne.symm hcy, Ne.symm hcz] have hηlt3 : η < 3 := by by_contra hnot have hη3 : η = 3 := by omega have huniv := hη_three_imp hη3 rcases hcover c huniv.1 huniv.2.1 huniv.2.2 with hcx' | hcy' | hcz' · exact hcx hcx' · exact hcy hcy' · exact hcz hcz' have hηdiv : η / 3 = 0 := Nat.div_eq_of_lt hηlt3 left rw [huse, hηdiv]
Finset.eq_univ_of_card- A subset of a finite type whose cardinality equals the cardinality of the type is the entire universe.
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.card_le_card- If s is a subset of t, then the cardinality of s is at most the cardinality of t.
Finset.card_pos.mp- If a finite set has strictly positive cardinality, then it is nonempty.
Finset.le_card_sdiff- The cardinality of a set difference t \ s is at least the cardinality of t minus the cardinality of s.
Finset.card_singleton- The cardinality of a singleton set {a} is 1.
Finset.mem_of_mem_erase- If an element belongs to s with a removed, it belongs to s.
Finset.ne_of_mem_erase- If b belongs to s with a removed, then b is not equal to a.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and does not belong to t.
Finset.card_pair- If a and b are distinct, then the set {a, b} has cardinality 2.
Finset.ssubset_iff_of_subset- If s is a subset of t, then s is a strictly proper subset of t if and only if there is an element in t not in s.
Finset.card_lt_card- If s is a strictly proper subset of t, then the cardinality of s is strictly less than the cardinality of t.
SimpleGraph.cycleGraph_three_eq_top- The cycle graph on 3 vertices C_3 is equal to the complete graph on 3 vertices.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Nat.ceilDiv_eq_add_pred_div- Ceiling division a ⌈/⌉ b equals (a + b - 1) / b for natural numbers.
cycle_three_proportionally_three_choosable_exists_distinct- From three finite sets of size 3, one can choose distinct representatives that cover their triple intersection.
cycle_three_proportionally_three_choosable_cycle_three_coloring_of_distinct- Any three pairwise distinct colors assigned to the vertices of C_3 define a proper coloring.
Finset.card_le_univ- The cardinality of any finite subset is at most the cardinality of the ambient universe.
cycle_three_proportionally_three_choosable_fin_three_filter_card_eq_three_iff- A filtered subset of Fin 3 has cardinality 3 if and only if the predicate holds on 0, 1, and 2.
Finset.card_pos.mpr- If a finite set is nonempty, then its cardinality is strictly positive.
cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one- For any natural number n with 0 < n ≤ 3, the ceiling division n ⌈/⌉ 3 equals 1.
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
Finset.filter_false_of_mem- Filtering a finite set by a predicate that holds for no element yields the empty set.
Nat.div_eq_of_lt- If a natural number a is strictly less than b, then integer division a / b equals 0.
- The cycle graph C_3 on three vertices is isomorphic to the complete graph K_3 (SimpleGraph.cycleGraph 3 = ⊤), so proper colorability is equivalent to choosing pairwise distinct colors for the three vertices.
- Because any proper coloring of C_3 uses each color at most once, the proportional choosability bounds are automatically satisfied for any color that appears in at most two lists (since 0 ≤ uses ≤ 1 falls between ⌊η/3⌋ and ⌈η/3⌉ when η ≤ 2). The only tight constraint is for colors present in all three lists (η = 3), which must be colored at least ⌈3/3⌉ = 1 time. This reduces the problem entirely to finding distinct representatives from the three lists that cover their triple intersection.
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.
/-- In a three-element universe, a filtered set has all three elements exactly when its card is three. -/private lemma cycle_three_proportionally_three_choosable_fin_three_filter_card_eq_three_iff {p : Fin 3 → Prop} [DecidablePred p] : (Finset.univ.filter p).card = 3 ↔ p 0 ∧ p 1 ∧ p 2 := by constructor · intro h have hs : Finset.univ.filter p = Finset.univ := by apply Finset.eq_univ_of_card simpa using h have hall : ∀ v : Fin 3, p v := by intro v have hv : v ∈ Finset.univ.filter p := by rw [hs] simp simpa using hv exact ⟨hall 0, hall 1, hall 2⟩ · rintro ⟨h0, h1, h2⟩ have hs : Finset.univ.filter p = Finset.univ := by ext v fin_cases v <;> simp [h0, h1, h2] rw [hs] simp/-- From three finite sets of size three one can choose distinct representatives covering their intersection. -/private lemma cycle_three_proportionally_three_choosable_exists_distinct {α : Type} [DecidableEq α] (A B C : Finset α) (hA : A.card = 3) (hB : B.card = 3) (hC : C.card = 3) : ∃ x y z : α, x ∈ A ∧ y ∈ B ∧ z ∈ C ∧ x ≠ y ∧ x ≠ z ∧ y ≠ z ∧ ∀ c : α, c ∈ A → c ∈ B → c ∈ C → c = x ∨ c = y ∨ c = z := by let U : Finset α := A ∩ B ∩ C have hUsubA : U ⊆ A := by intro a ha simp only [U, Finset.mem_inter] at ha exact ha.1.1 have hUsubB : U ⊆ B := by intro a ha simp only [U, Finset.mem_inter] at ha exact ha.1.2 have hUsubC : U ⊆ C := by intro a ha simp only [U, Finset.mem_inter] at ha exact ha.2 have hUcard : U.card ≤ 3 := by calc U.card ≤ A.card := Finset.card_le_card hUsubA _ = 3 := hA have hx_exists : ∃ x, x ∈ A ∧ (U.Nonempty → x ∈ U) := by by_cases hUne : U.Nonempty · obtain ⟨x, hxU⟩ := hUne.exists_mem exact ⟨x, hUsubA hxU, fun _ => hxU⟩ · have hApos : 0 < A.card := by omega obtain ⟨x, hxA⟩ := Finset.card_pos.mp hApos exact ⟨x, hxA, fun h => (hUne h).elim⟩ obtain ⟨x, hxA, hxUcond⟩ := hx_exists have hy_base : (B \ {x}).Nonempty := by have hle := Finset.le_card_sdiff ({x} : Finset α) B rw [Finset.card_singleton, hB] at hle have hpos : 0 < (B \ {x}).card := by omega exact Finset.card_pos.mp hpos have hy_exists : ∃ y, y ∈ B ∧ y ≠ x ∧ ((U.erase x).Nonempty → y ∈ U.erase x) := by by_cases hUx : (U.erase x).Nonempty · obtain ⟨y, hyUx⟩ := hUx.exists_mem exact ⟨y, hUsubB (Finset.mem_of_mem_erase hyUx), Finset.ne_of_mem_erase hyUx, fun _ => hyUx⟩ · obtain ⟨y, hyBdiff⟩ := hy_base rw [Finset.mem_sdiff] at hyBdiff exact ⟨y, hyBdiff.1, by simpa using hyBdiff.2, fun h => (hUx h).elim⟩ obtain ⟨y, hyB, hyx, hyUcond⟩ := hy_exists have hxy : x ≠ y := hyx.symm have hz_base : (C \ ({x, y} : Finset α)).Nonempty := by have hle := Finset.le_card_sdiff ({x, y} : Finset α) C rw [Finset.card_pair hxy, hC] at hle have hpos : 0 < (C \ ({x, y} : Finset α)).card := by omega exact Finset.card_pos.mp hpos have hz_exists : ∃ z, z ∈ C ∧ z ≠ x ∧ z ≠ y ∧ ((U \ ({x, y} : Finset α)).Nonempty → z ∈ U \ ({x, y} : Finset α)) := by by_cases hUxy : (U \ ({x, y} : Finset α)).Nonempty · obtain ⟨z, hzUxy⟩ := hUxy.exists_mem rw [Finset.mem_sdiff] at hzUxy have hzx : z ≠ x := by intro hzx exact hzUxy.2 (by simp [hzx]) have hzy : z ≠ y := by intro hzy exact hzUxy.2 (by simp [hzy]) exact ⟨z, hUsubC hzUxy.1, hzx, hzy, fun _ => by rw [Finset.mem_sdiff] exact hzUxy⟩ · obtain ⟨z, hzCdiff⟩ := hz_base rw [Finset.mem_sdiff] at hzCdiff have hzx : z ≠ x := by intro hzx exact hzCdiff.2 (by simp [hzx]) have hzy : z ≠ y := by intro hzy exact hzCdiff.2 (by simp [hzy]) exact ⟨z, hzCdiff.1, hzx, hzy, fun h => (hUxy h).elim⟩ obtain ⟨z, hzC, hzx, hzy, hzUcond⟩ := hz_exists have hxz : x ≠ z := hzx.symm have hyz : y ≠ z := hzy.symm have hcard3 : ({x, y, z} : Finset α).card = 3 := by exact Finset.card_eq_three.mpr ⟨x, y, z, hxy, hxz, hyz, rfl⟩ refine ⟨x, y, z, hxA, hyB, hzC, hxy, hxz, hyz, ?_⟩ intro c hcA hcB hcC have hcU : c ∈ U := by simp only [U, Finset.mem_inter] exact ⟨⟨hcA, hcB⟩, hcC⟩ by_cases hcx : c = x · exact Or.inl hcx · by_cases hcy : c = y · exact Or.inr (Or.inl hcy) · right; right by_contra hcz have hUxne : (U.erase x).Nonempty := ⟨c, Finset.mem_erase.mpr ⟨hcx, hcU⟩⟩ have hyUx := hyUcond hUxne have hyU : y ∈ U := Finset.mem_of_mem_erase hyUx have hcnotxy : c ∉ ({x, y} : Finset α) := by simp [hcx, hcy] have hUxyne : (U \ ({x, y} : Finset α)).Nonempty := ⟨c, Finset.mem_sdiff.mpr ⟨hcU, hcnotxy⟩⟩ have hzUxy := hzUcond hUxyne have hzU : z ∈ U := (Finset.mem_sdiff.mp hzUxy).1 have hxU : x ∈ U := hxUcond ⟨c, hcU⟩ have hsub : ({x, y, z} : Finset α) ⊆ U := by intro a ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl · exact hxU · exact hyU · exact hzU have hcnot : c ∉ ({x, y, z} : Finset α) := by simp [hcx, hcy, hcz] have hssub : ({x, y, z} : Finset α) ⊂ U := (Finset.ssubset_iff_of_subset hsub).mpr ⟨c, hcU, hcnot⟩ have hlt := Finset.card_lt_card hssub rw [hcard3] at hlt omega/-- A triangle can be properly colored by any three pairwise distinct colors. -/private lemma cycle_three_proportionally_three_choosable_cycle_three_coloring_of_distinct {α : Type} (x y z : α) (hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z) : ∃ f : (SimpleGraph.cycleGraph 3).Coloring α, f 0 = x ∧ f 1 = y ∧ f 2 = z := by refine ⟨SimpleGraph.Coloring.mk (![x, y, z] : Fin 3 → α) ?_, ?_, ?_, ?_⟩ · intro v w h rw [SimpleGraph.cycleGraph_three_eq_top] at h fin_cases v <;> fin_cases w <;> simp_all [Ne.symm] · rfl · rfl · rfl/-- The ceiling division of a positive natural at most three by three is one. -/private lemma cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one {n : ℕ} (h0 : 0 < n) (h3 : n ≤ 3) : n ⌈/⌉ 3 = 1 := by rw [Nat.ceilDiv_eq_add_pred_div] interval_cases n <;> norm_num/-- The triangle cycle C_3 is proportionally 3-choosable (special case n = 3 of OP-593). -/theorem cycle_three_proportionally_three_choosable : ∀ (α : Type) [Fintype α] [DecidableEq α] (L : Fin 3 → Finset α), (∀ v, (L v).card = 3) → ∃ f : (SimpleGraph.cycleGraph 3).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 = η / 3 ∨ uses = η ⌈/⌉ 3 := by intro α _ _ L hL obtain ⟨x, y, z, hxA, hyB, hzC, hxy, hxz, hyz, hcover⟩ := cycle_three_proportionally_three_choosable_exists_distinct (L 0) (L 1) (L 2) (hL 0) (hL 1) (hL 2) obtain ⟨f, hf0, hf1, hf2⟩ := cycle_three_proportionally_three_choosable_cycle_three_coloring_of_distinct x y z hxy hxz hyz refine ⟨f, ?_, ?_⟩ · intro v fin_cases v · simpa [hf0] using hxA · simpa [hf1] using hyB · simpa [hf2] using hzC · intro c dsimp only set η : ℕ := (Finset.univ.filter (fun v : Fin 3 => c ∈ L v)).card with hηdef set uses : ℕ := (Finset.univ.filter (fun v : Fin 3 => f v = c)).card with husesdef change uses = η / 3 ∨ uses = η ⌈/⌉ 3 have hηle : η ≤ 3 := by rw [hηdef] simpa using Finset.card_le_univ (Finset.univ.filter (fun v : Fin 3 => c ∈ L v)) have hη_three_imp : η = 3 → c ∈ L 0 ∧ c ∈ L 1 ∧ c ∈ L 2 := by intro hη3 have hcard : (Finset.univ.filter (fun v : Fin 3 => c ∈ L v)).card = 3 := by rw [hηdef] at hη3 exact hη3 exact (cycle_three_proportionally_three_choosable_fin_three_filter_card_eq_three_iff (p := fun v : Fin 3 => c ∈ L v)).mp hcard have huse_x : (Finset.univ.filter (fun v : Fin 3 => f v = x)).card = 1 := by rw [show (Finset.univ.filter (fun v : Fin 3 => f v = x)) = {0} by ext v fin_cases v <;> simp [hf0, hf1, hf2, Ne.symm hxy, Ne.symm hxz]] simp have huse_y : (Finset.univ.filter (fun v : Fin 3 => f v = y)).card = 1 := by rw [show (Finset.univ.filter (fun v : Fin 3 => f v = y)) = {1} by ext v fin_cases v <;> simp [hf0, hf1, hf2, hxy, Ne.symm hyz]] simp have huse_z : (Finset.univ.filter (fun v : Fin 3 => f v = z)).card = 1 := by rw [show (Finset.univ.filter (fun v : Fin 3 => f v = z)) = {2} by ext v fin_cases v <;> simp [hf0, hf1, hf2, hxz, hyz]] simp by_cases hcx : c = x · subst c have huse : uses = 1 := by rw [husesdef] exact huse_x have hηpos : 0 < η := by rw [hηdef] apply Finset.card_pos.mpr exact ⟨0, by simp [hxA]⟩ have hceil : η ⌈/⌉ 3 = 1 := cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one hηpos hηle right rw [huse, hceil] · by_cases hcy : c = y · subst c have huse : uses = 1 := by rw [husesdef] exact huse_y have hηpos : 0 < η := by rw [hηdef] apply Finset.card_pos.mpr exact ⟨1, by simp [hyB]⟩ have hceil : η ⌈/⌉ 3 = 1 := cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one hηpos hηle right rw [huse, hceil] · by_cases hcz : c = z · subst c have huse : uses = 1 := by rw [husesdef] exact huse_z have hηpos : 0 < η := by rw [hηdef] apply Finset.card_pos.mpr exact ⟨2, by simp [hzC]⟩ have hceil : η ⌈/⌉ 3 = 1 := cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one hηpos hηle right rw [huse, hceil] · have huse : uses = 0 := by rw [husesdef, Finset.card_eq_zero] apply Finset.filter_false_of_mem intro v _ fin_cases v <;> simp [hf0, hf1, hf2, Ne.symm hcx, Ne.symm hcy, Ne.symm hcz] have hηlt3 : η < 3 := by by_contra hnot have hη3 : η = 3 := by omega have huniv := hη_three_imp hη3 rcases hcover c huniv.1 huniv.2.1 huniv.2.2 with hcx' | hcy' | hcz' · exact hcx hcx' · exact hcy hcy' · exact hcz hcz' have hηdiv : η / 3 = 0 := Nat.div_eq_of_lt hηlt3 left rw [huse, hηdiv]