AFTD Auto-Formalizing Theoretical Domains

cycle_three_proportionally_three_choosable

theoremverified

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.

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

    lines 5–22

    uses Finset.eq_univ_of_card

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

    lines 32–47

    uses Finset.mem_inter, Finset.card_le_card

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

    lines 48–55

    uses Finset.card_pos.mp

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

    lines 56–70

    uses Finset.le_card_sdiff, Finset.card_singleton, Finset.card_pos.mp, Finset.mem_of_mem_erase, Finset.ne_of_mem_erase, Finset.mem_sdiff

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

    lines 71–103

    uses Finset.le_card_sdiff, Finset.card_pair, Finset.card_pos.mp, Finset.mem_sdiff

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

    lines 104–138

    uses Finset.mem_inter, Finset.mem_of_mem_erase, Finset.ssubset_iff_of_subset, Finset.card_lt_card

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

    lines 145–151

    uses SimpleGraph.cycleGraph_three_eq_top, Ne.symm

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

    lines 156–157

    uses Nat.ceilDiv_eq_add_pred_div

      rw [Nat.ceilDiv_eq_add_pred_div]
      interval_cases n <;> norm_num
  9. 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.

    lines 169–180

    uses cycle_three_proportionally_three_choosable_exists_distinct, cycle_three_proportionally_three_choosable_cycle_three_coloring_of_distinct

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

    lines 181–210

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

    lines 211–249

    uses Finset.card_pos.mpr, cycle_three_proportionally_three_choosable_ceilDiv_three_eq_one

        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]
  12. 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⌋.

    lines 250–265

    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.

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

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