AFTD Auto-Formalizing Theoretical Domains

odd_antihole_colorable_of_common_palette

theoremverifiedformalization

Theorem 8 of arXiv:2610.14241 for the odd antihole: for ℓ ≥ 3, if all lists of an (ℓ-1)-assignment of complement(C_{2ℓ-1}) are subsets of a common ℓ-set P and are not all identical, then the antihole is L-colorable.

Statement

theorem odd_antihole_colorable_of_common_palette (ℓ : ℕ) (hℓ : 3 ≤ ℓ) (P : Finset ℕ)
    (hP : P.card = ℓ) (L : Fin (2 * ℓ - 1) → Finset ℕ) (hL : ∀ v, (L v).card = ℓ - 1)
    (hLP : ∀ v, L v ⊆ P) (hne : ∃ u v, L u ≠ L v) :
    ∃ c : Fin (2 * ℓ - 1) → ℕ, (∀ v, c v ∈ L v) ∧
      ∀ u v, (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Adj u v → c u ≠ c v
Formalizes
arXiv:2610.14241 (Restricting odd antiholes in critical graphs via list coloring), Theorem 8, specialized to G = complement of C_{2ℓ-1} (whose complement, the odd cycle, is hypomatchable); partial result for OP-216 (the conjecture with the common-palette assumption)
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

The proof, explained

For the odd antihole complement(C_{2ℓ-1}), independent sets correspond to cliques of C_{2ℓ-1}, which are singletons and adjacent edges; thus an ℓ-coloring partitions vertices into one singleton {s} and ℓ - 1 consecutive cycle pairs {s + 2j - 1, s + 2j}. Since each list L(v) has size ℓ - 1 from a common ℓ-set P, each L(v) excludes a single color μ(v) ∈ P, so finding a color for each of the ℓ classes reduces to a system of distinct representatives problem governed by Hall's Marriage Theorem. A base vertex s is called Good when its pairing satisfies Hall's condition; if no vertex were Good, a counting argument on the frequencies of excluded colors shows that three distinct colors would each appear at least ℓ - 1 times, exceeding the total number of vertices 2ℓ - 1. Therefore a Good base vertex s must exist, yielding an injective selector via Hall's theorem that properly colors the antihole.

  1. Every vertex v can be assigned to a class j(v) = ((v - s).val + 1) / 2 < ℓ, yielding a candidate coloring c(v) = f(j(v)).

    The offset (v - s).val is strictly less than 2ℓ - 1, which implies ((v - s).val + 1) / 2 < ℓ by linear integer arithmetic (omega). We define the candidate coloring c by evaluating the injective selector f on the class index j(v).

    lines 11–15

      have hcls : ∀ v : Fin (2 * ℓ - 1), ((v - s).val + 1) / 2 < ℓ := by
        intro v
        have := (v - s).isLt
        omega
      refine ⟨fun v => f ⟨((v - s).val + 1) / 2, hcls v⟩, ?_, ?_⟩
  2. The candidate coloring satisfies the list constraints: c(v) ∈ L(v) for every vertex v.

    For any vertex v, 2 * j(v) is either (v - s).val or (v - s).val + 1, so (v - s).val is either 2 * j(v) - 1 or 2 * j(v). Since s + (v - s) = v, vertex v is one of s + 2*j(v) - 1 or s + 2*j(v). By the hypothesis on f, the color f(j(v)) belongs to both L(s + 2*j(v) - 1) and L(s + 2*j(v)), and therefore f(j(v)) ∈ L(v).

    lines 16–30

    uses Fin.cast_val_eq_self, Finset.mem_inter

      · intro v
        have hv : s + (((v - s).val : ℕ) : Fin (2 * ℓ - 1)) = v := by
          rw [Fin.cast_val_eq_self]
          abel
        have h := hft ⟨((v - s).val + 1) / 2, hcls v⟩
        simp only [Finset.mem_inter] at h
        have key : 2 * (((v - s).val + 1) / 2) - 1 = (v - s).val ∨
            2 * (((v - s).val + 1) / 2) = (v - s).val := by omega
        rcases key with k | k
        · have h1 := h.1
          rw [k, hv] at h1
          exact h1
        · have h2 := h.2
          rw [k, hv] at h2
          exact h2
  3. The candidate coloring is a proper coloring of the antihole complement(C_{2ℓ-1}): if u and v are adjacent in the antihole, then c(u) ≠ c(v).

    Two vertices are adjacent in the antihole if and only if they are distinct and not adjacent in the cycle C_{2ℓ-1}. If c(u) = c(v), injectivity of f implies j(u) = j(v). Because u ≠ v, their offsets (u - s).val and (v - s).val are distinct natural numbers with equal halves, forcing one to be the other plus 1. Therefore u - v = ±1 modulo 2ℓ - 1, meaning u and v are adjacent in C_{2ℓ-1}, contradicting antihole adjacency.

    lines 31–57

    uses SimpleGraph.compl_adj, SimpleGraph.cycleGraph_adj', Fin.ext, Fin.sub_def, Nat.add_mod_right, Nat.mod_eq_of_lt

      · intro u v hadj heq
        rw [SimpleGraph.compl_adj] at hadj
        obtain ⟨hne, hnadj⟩ := hadj
        apply hnadj
        have heq' := Fin.mk.inj_iff.mp (hf heq)
        rw [SimpleGraph.cycleGraph_adj']
        have hij : (u - s).val ≠ (v - s).val := by
          intro h
          apply hne
          have : u - s = v - s := Fin.ext h
          simpa using this
        have hsub : u - v = (u - s) - (v - s) := by abel
        have hsub' : v - u = (v - s) - (u - s) := by abel
        rw [hsub, hsub']
        have hu := (u - s).isLt
        have hv := (v - s).isLt
        rcases (show (u - s).val = (v - s).val + 1 ∨ (v - s).val = (u - s).val + 1 by omega) with h | h
        · left
          rw [Fin.sub_def]
          simp only
          rw [h, show 2 * ℓ - 1 - (v - s).val + ((v - s).val + 1) = 1 + (2 * ℓ - 1) by omega,
            Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)]
        · right
          rw [Fin.sub_def]
          simp only
          rw [h, show 2 * ℓ - 1 - (u - s).val + ((u - s).val + 1) = 1 + (2 * ℓ - 1) by omega,
            Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)]
  4. For each class index j, the set of available colors t(j) = P \ {a(j), b(j)} satisfies |t(j)| ≥ ℓ - 2, and the base class satisfies |t(0)| ≥ ℓ - 1.

    Hall's Marriage Theorem (via Finset.all_card_le_biUnion_card_iff_exists_injective) reduces the existence of an injective selector f to checking |S| ≤ |⋃_{j ∈ S} t(j)| for all S ⊆ Fin ℓ. Removing at most two elements from P (which has size ℓ) leaves at least ℓ - 2 elements. At j = 0, since a(0) = b(0), only one element is removed, leaving at least ℓ - 1 elements.

    lines 67–88

    uses Finset.all_card_le_biUnion_card_iff_exists_injective, Finset.mem_erase, Finset.mem_inter, Finset.pred_card_le_card_erase, Finset.card_le_card

      classical
      set t : Fin ℓ → Finset ℕ := fun j => P.erase (a j.val) ∩ P.erase (b j.val) with ht_def
      apply (Finset.all_card_le_biUnion_card_iff_exists_injective t).mp
      have ht : ∀ j, ℓ - 2 ≤ (t j).card := by
        intro j
        have h1 : (P.erase (a j.val)).erase (b j.val) ⊆ t j := by
          intro x hx
          simp only [Finset.mem_erase] at hx
          simp only [ht_def, Finset.mem_inter, Finset.mem_erase]
          tauto
        have h2 := Finset.pred_card_le_card_erase (s := P.erase (a j.val)) (a := b j.val)
        have h3 := Finset.pred_card_le_card_erase (s := P) (a := a j.val)
        have h4 := Finset.card_le_card h1
        omega
      have ht0 : ℓ - 1 ≤ (t ⟨0, by omega⟩).card := by
        have hsub : P.erase (a 0) ⊆ t ⟨0, by omega⟩ := by
          intro x hx
          simp only [ht_def, Finset.mem_inter]
          exact ⟨hx, by rw [← h0]; exact hx⟩
        have := Finset.card_le_card hsub
        have := Finset.pred_card_le_card_erase (s := P) (a := a 0)
        omega
  5. Hall's condition holds for all subsets S ⊆ Fin ℓ with |S| ≤ ℓ - 2, and for all S containing 0.

    If |S| ≤ ℓ - 2, the condition is immediate: if S is nonempty, any single element j ∈ S already has |t(j)| ≥ ℓ - 2 ≥ |S|. If 0 ∈ S and |S| ≤ ℓ - 1, the single set t(0) already provides at least ℓ - 1 colors. If 0 ∈ S and |S| = ℓ, then S = Fin ℓ; any color x ∈ P with x ≠ a(0) is in t(0), while x = a(0) is in t(k) for some k by hypothesis hA. Thus P ⊆ ⋃_{j ∈ S} t(j), so the union has size ℓ = |S|.

    lines 89–114

    uses Finset.card_le_univ, Finset.card_le_card, Finset.subset_biUnion_of_mem, Finset.eq_univ_of_card, Finset.mem_biUnion, Finset.mem_erase, Finset.mem_inter, Finset.mem_univ

      intro S
      have hSle : S.card ≤ ℓ := by simpa using Finset.card_le_univ S
      by_cases hS : S.card ≤ ℓ - 2
      · rcases S.eq_empty_or_nonempty with rfl | ⟨j, hj⟩
        · simp
        · exact hS.trans ((ht j).trans (Finset.card_le_card (Finset.subset_biUnion_of_mem t hj)))
      by_cases h0S : (⟨0, by omega⟩ : Fin ℓ) ∈ S
      · by_cases hSf : S.card = ℓ
        · have hSu : S = Finset.univ := Finset.eq_univ_of_card S (by simpa using hSf)
          have hPsub : P ⊆ S.biUnion t := by
            intro x hx
            rw [Finset.mem_biUnion]
            by_cases hx0 : x = a 0
            · obtain ⟨k, hk1, hk2, hak, hbk⟩ := hA
              refine ⟨⟨k, hk2⟩, by rw [hSu]; exact Finset.mem_univ _, ?_⟩
              simp only [ht_def, Finset.mem_inter, Finset.mem_erase]
              rw [hx0] at hx ⊢
              exact ⟨⟨hak, hx⟩, ⟨hbk, hx⟩⟩
            · refine ⟨⟨0, by omega⟩, h0S, ?_⟩
              simp only [ht_def, Finset.mem_inter, Finset.mem_erase]
              exact ⟨⟨hx0, hx⟩, ⟨by rw [← h0]; exact hx0, hx⟩⟩
          calc S.card = ℓ := hSf
            _ = P.card := hP.symm
            _ ≤ _ := Finset.card_le_card hPsub
        · have : S.card ≤ ℓ - 1 := by omega
          exact this.trans (ht0.trans (Finset.card_le_card (Finset.subset_biUnion_of_mem t h0S)))
  6. Hall's condition holds for S = (Fin ℓ) \ {0}, completing the proof of Hall's condition for all subsets S.

    When 0 ∉ S and |S| ≥ ℓ - 1, S must be exactly the complement of {0}, so |S| = ℓ - 1, and the two indices k₁, k₂ from hypothesis hB both belong to S. Case analysis on hB shows that t(k₁) ∪ t(k₂) contains all of P except possibly one element: if a(k₁) = b(k₁), erasing a(k₁) gives a subset of t(k₁); if a(k₂) ∉ {a(k₁), b(k₁)}, erasing b(k₂) is contained in t(k₁) ∪ t(k₂); otherwise erasing a(k₂) is contained in the union. In every case, |⋃_{j ∈ S} t(j)| ≥ |P| - 1 = ℓ - 1 = |S|.

    lines 115–175

    uses Finset.mem_erase, Finset.mem_univ, Finset.eq_of_subset_of_card_le, Finset.card_erase_of_mem, Finset.card_univ, Fintype.card_fin, Fin.ext_iff, Finset.subset_biUnion_of_mem, Finset.mem_union_left, Finset.mem_union_right, Finset.mem_inter, Finset.union_subset, Finset.card_le_card, Finset.pred_card_le_card_erase

      · obtain ⟨k₁, k₂, hk1, hk1', hk2, hk2', hcase⟩ := hB
        have hSsub : S ⊆ Finset.univ.erase ⟨0, by omega⟩ := by
          intro j hj
          rw [Finset.mem_erase]
          exact ⟨fun h => h0S (h ▸ hj), Finset.mem_univ _⟩
        have hSeq : S = Finset.univ.erase ⟨0, by omega⟩ := by
          apply Finset.eq_of_subset_of_card_le hSsub
          rw [Finset.card_erase_of_mem (Finset.mem_univ _)]
          simp only [Finset.card_univ, Fintype.card_fin]
          omega
        have hm1 : (⟨k₁, hk1'⟩ : Fin ℓ) ∈ S := by
          rw [hSeq, Finset.mem_erase]
          refine ⟨?_, Finset.mem_univ _⟩
          intro h
          simp only [Fin.ext_iff] at h
          omega
        have hm2 : (⟨k₂, hk2'⟩ : Fin ℓ) ∈ S := by
          rw [hSeq, Finset.mem_erase]
          refine ⟨?_, Finset.mem_univ _⟩
          intro h
          simp only [Fin.ext_iff] at h
          omega
        have hsub1 := Finset.subset_biUnion_of_mem t hm1
        have hsub2 := Finset.subset_biUnion_of_mem t hm2
        have key : ∃ m, P.erase m ⊆ t ⟨k₁, hk1'⟩ ∪ t ⟨k₂, hk2'⟩ := by
          rcases hcase with h | ⟨h1, h2⟩ | ⟨h1, h2⟩
          · refine ⟨a k₁, ?_⟩
            intro x hx
            apply Finset.mem_union_left
            simp only [Finset.mem_erase] at hx
            simp only [ht_def, Finset.mem_inter, Finset.mem_erase]
            exact ⟨hx, ⟨by rw [← h]; exact hx.1, hx.2⟩⟩
          · refine ⟨b k₂, ?_⟩
            intro x hx
            simp only [Finset.mem_erase] at hx
            by_cases hxa : x = a k₂
            · apply Finset.mem_union_left
              simp only [ht_def, Finset.mem_inter, Finset.mem_erase]
              rw [hxa] at hx ⊢
              exact ⟨⟨h1, hx.2⟩, ⟨h2, hx.2⟩⟩
            · apply Finset.mem_union_right
              simp only [ht_def, Finset.mem_inter, Finset.mem_erase]
              exact ⟨⟨hxa, hx.2⟩, hx⟩
          · refine ⟨a k₂, ?_⟩
            intro x hx
            simp only [Finset.mem_erase] at hx
            by_cases hxb : x = b k₂
            · apply Finset.mem_union_left
              simp only [ht_def, Finset.mem_inter, Finset.mem_erase]
              rw [hxb] at hx ⊢
              exact ⟨⟨h1, hx.2⟩, ⟨h2, hx.2⟩⟩
            · apply Finset.mem_union_right
              simp only [ht_def, Finset.mem_inter, Finset.mem_erase]
              exact ⟨hx, ⟨hxb, hx.2⟩⟩
        obtain ⟨m, hm⟩ := key
        have hScard : S.card = ℓ - 1 := by
          rw [hSeq, Finset.card_erase_of_mem (Finset.mem_univ _)]
          simp only [Finset.card_univ, Fintype.card_fin]
        have := Finset.card_le_card (hm.trans (Finset.union_subset hsub1 hsub2))
        have := Finset.pred_card_le_card_erase (s := P) (a := m)
        omega
  7. If a color c appears in every pairing class with index in [lo, ℓ), then at least ℓ - lo vertices have excluded color c.

    Define a function g on the interval [lo, ℓ) that selects, for each index k, one vertex from {s + 2k - 1, s + 2k} with excluded color c. Because the classes are disjoint along the cycle, g is an injection into the set of vertices of color c. Therefore |{v | μ(v) = c}| ≥ |[lo, ℓ)| = ℓ - lo.

    lines 185–206

    uses add_left_cancel, congrArg, Fin.val_cast_of_lt, Finset.card_le_card_of_injOn, Finset.coe_Ico, Set.mem_Ico, Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq, Or.resolve_right

      have hw : ∀ i j : ℕ, i < 2 * ℓ - 1 → j < 2 * ℓ - 1 →
          s + ((i : ℕ) : Fin (2 * ℓ - 1)) = s + ((j : ℕ) : Fin (2 * ℓ - 1)) → i = j := by
        intro i j hi hj hij
        have h' := add_left_cancel hij
        have := congrArg Fin.val h'
        rwa [Fin.val_cast_of_lt hi, Fin.val_cast_of_lt hj] at this
      let g : ℕ → Fin (2 * ℓ - 1) := fun k =>
        if μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) = c then s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))
        else s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1))
      have hle := Finset.card_le_card_of_injOn g (s := Finset.Ico lo ℓ)
        (t := Finset.univ.filter (fun v => μ v = c)) ?_ ?_
      · simpa using hle
      · intro k hk
        simp only [Finset.coe_Ico, Set.mem_Ico] at hk
        simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq, g]
        split_ifs with h1
        · exact h1
        · exact (h k hk.1 hk.2).resolve_right h1
      · intro k1 hk1 k2 hk2 heq
        simp only [Finset.coe_Ico, Set.mem_Ico] at hk1 hk2
        simp only [g] at heq
        split_ifs at heq <;> (have := hw _ _ (by omega) (by omega) heq; omega)
  8. Three pairwise distinct colors have at most 2ℓ - 1 vertices in total.

    The fibers of three distinct colors under μ are pairwise disjoint subsets of the vertex set Fin (2ℓ - 1). The cardinality of their union is the sum of their individual cardinalities, which cannot exceed the total number of vertices 2ℓ - 1.

    lines 213–233

    uses Finset.disjoint_filter, Finset.disjoint_union_left, Finset.card_union_of_disjoint, Finset.card_le_univ, Fintype.card_fin

      have d1 : Disjoint (Finset.univ.filter (fun v => μ v = a))
          (Finset.univ.filter (fun v => μ v = b)) := by
        rw [Finset.disjoint_filter]
        intro x _ h1 h2
        exact hab (h1.symm.trans h2)
      have d2 : Disjoint (Finset.univ.filter (fun v => μ v = a) ∪
          Finset.univ.filter (fun v => μ v = b)) (Finset.univ.filter (fun v => μ v = c)) := by
        rw [Finset.disjoint_union_left]
        constructor
        · rw [Finset.disjoint_filter]
          intro x _ h1 h2
          exact hac (h1.symm.trans h2)
        · rw [Finset.disjoint_filter]
          intro x _ h1 h2
          exact hbc (h1.symm.trans h2)
      have e1 := Finset.card_union_of_disjoint d1
      have e2 := Finset.card_union_of_disjoint d2
      have e3 := Finset.card_le_univ (Finset.univ.filter (fun v => μ v = a) ∪
          Finset.univ.filter (fun v => μ v = b) ∪ Finset.univ.filter (fun v => μ v = c))
      rw [Fintype.card_fin] at e3
      omega
  9. Two distinct colors have at most 2ℓ - 1 vertices in total.

    The fibers of two distinct colors under μ are disjoint subsets of Fin (2ℓ - 1). Their combined size is the cardinality of their union, which is at most the total number of vertices 2ℓ - 1.

    lines 240–249

    uses Finset.disjoint_filter, Finset.card_union_of_disjoint, Finset.card_le_univ, Fintype.card_fin

      have d1 : Disjoint (Finset.univ.filter (fun v => μ v = a))
          (Finset.univ.filter (fun v => μ v = b)) := by
        rw [Finset.disjoint_filter]
        intro x _ h1 h2
        exact hab (h1.symm.trans h2)
      have e1 := Finset.card_union_of_disjoint d1
      have e3 := Finset.card_le_univ (Finset.univ.filter (fun v => μ v = a) ∪
          Finset.univ.filter (fun v => μ v = b))
      rw [Fintype.card_fin] at e3
      omega
  10. Each list L(v) is P \ {μ(v)} for a unique color μ(v) ∈ P; we define the frequency F(c) and the class colors A(s, k), B(s, k).

    Since each L(v) has size ℓ - 1 and is a subset of P of size ℓ, the relative complement P \ L(v) is a singleton {μ(v)}, so L(v) = P \ {μ(v)}. For any base vertex s and index k, A(s, k) and B(s, k) record the excluded colors at vertices s + 2k - 1 and s + 2k, with A(s, 0) = B(s, 0) = μ(s). F(c) is defined as the number of vertices v with μ(v) = c.

    lines 256–288

    uses Finset.card_sdiff_of_subset, Finset.card_eq_one, Finset.mem_singleton_self, Finset.mem_sdiff, Finset.mem_erase, Finset.mem_singleton

      classical
      have : NeZero (2 * ℓ - 1) := ⟨by omega⟩
      letI : NatCast (Fin (2 * ℓ - 1)) := Fin.NatCast.instNatCast (2 * ℓ - 1)
      -- each list is the palette minus one colour `μ v`
      have hμ : ∀ v, ∃ m, m ∈ P ∧ L v = P.erase m := by
        intro v
        have hc : (P \ L v).card = 1 := by
          rw [Finset.card_sdiff_of_subset (hLP v), hP, hL]
          omega
        obtain ⟨m, hm⟩ := Finset.card_eq_one.mp hc
        have hmP : m ∈ P ∧ m ∉ L v := by
          have : m ∈ P \ L v := by rw [hm]; exact Finset.mem_singleton_self m
          exact Finset.mem_sdiff.mp this
        refine ⟨m, hmP.1, ?_⟩
        ext x
        rw [Finset.mem_erase]
        constructor
        · intro hx
          exact ⟨fun h => hmP.2 (h ▸ hx), hLP v hx⟩
        · rintro ⟨hxm, hxP⟩
          by_contra hxL
          have : x ∈ P \ L v := Finset.mem_sdiff.mpr ⟨hxP, hxL⟩
          rw [hm, Finset.mem_singleton] at this
          exact hxm this
      choose μ _ hμL using hμ
      obtain ⟨F, hF⟩ : ∃ F : ℕ → ℕ, ∀ c, F c = (Finset.univ.filter (fun v => μ v = c)).card :=
        ⟨_, fun _ => rfl⟩
      obtain ⟨A, hA⟩ : ∃ A : Fin (2 * ℓ - 1) → ℕ → ℕ,
          ∀ s k, A s k = μ (s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1))) := ⟨_, fun _ _ => rfl⟩
      obtain ⟨B, hB⟩ : ∃ B : Fin (2 * ℓ - 1) → ℕ → ℕ,
          ∀ s k, B s k = μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) := ⟨_, fun _ _ => rfl⟩
      have hA0 : ∀ s, A s 0 = μ s := fun s => by rw [hA]; simp
      have hB0 : ∀ s, B s 0 = μ s := fun s => by rw [hB]; simp
  11. The frequency function F satisfies positivity, sum bounds for two and three colors, and class-coverage lower bounds.

    Every vertex v contributes to F(μ(v)), so F(μ(v)) ≥ 1. For distinct colors, the sum bounds F(a) + F(b) ≤ 2ℓ - 1 and F(a) + F(b) + F(c) ≤ 2ℓ - 1 follow directly from the disjointness lemmas. If a color c appears in every class from lo to ℓ - 1, the counting lemma implies ℓ - lo ≤ F(c).

    lines 289–308

    uses Finset.card_pos, odd_antihole_colorable_of_common_palette_sum2, odd_antihole_colorable_of_common_palette_sum3, odd_antihole_colorable_of_common_palette_count

      have hF1 : ∀ v, 1 ≤ F (μ v) := by
        intro v
        rw [hF]
        exact Finset.card_pos.mpr ⟨v, by simp⟩
      have hsum2 : ∀ a b, a ≠ b → F a + F b ≤ 2 * ℓ - 1 := by
        intro a b h
        rw [hF, hF]
        exact odd_antihole_colorable_of_common_palette_sum2 μ a b h
      have hsum3 : ∀ a b c, a ≠ b → a ≠ c → b ≠ c → F a + F b + F c ≤ 2 * ℓ - 1 := by
        intro a b c h1 h2 h3
        rw [hF, hF, hF]
        exact odd_antihole_colorable_of_common_palette_sum3 μ a b c h1 h2 h3
      have hcount : ∀ s c lo, (∀ k, lo ≤ k → k < ℓ → A s k = c ∨ B s k = c) → ℓ - lo ≤ F c := by
        intro s c lo h
        rw [hF]
        apply odd_antihole_colorable_of_common_palette_count ℓ hℓ μ s c lo
        intro k h1 h2
        rw [← hA, ← hB]
        exact h k h1 h2
      -- a pairing is good when Hall's condition holds for it
  12. If a base vertex s is not Good, then either F(μ(s)) ≥ ℓ, or there is a color b such that μ(s), A(s, 1), and b are pairwise distinct and both F(A(s, 1)) ≥ ℓ - 1 and F(b) ≥ ℓ - 1.

    A vertex s is Good if the pairing at s satisfies both hypotheses hA and hB of Hall's lemma. If hA fails, μ(s) appears in every class k ∈ [0, ℓ), so F(μ(s)) ≥ ℓ. If hB fails, every class k ∈ [1, ℓ) must have A(s, k) ≠ B(s, k) and must equal the pair {A(s, 1), B(s, 1)}. Hence both A(s, 1) and B(s, 1) appear in all ℓ - 1 classes, giving frequencies at least ℓ - 1. If μ(s) matches either of them, that color also appears in class 0, giving frequency at least ℓ; otherwise μ(s), A(s, 1), and b = B(s, 1) are three pairwise distinct colors.

    lines 309–384

    uses not_and_or, Ne.symm, le_refl, Or.inl, Or.inr, le_rfl

      let Good : Fin (2 * ℓ - 1) → Prop := fun s =>
        (∃ k, 1 ≤ k ∧ k < ℓ ∧ A s 0 ≠ A s k ∧ A s 0 ≠ B s k) ∧
        (∃ k₁ k₂, 1 ≤ k₁ ∧ k₁ < ℓ ∧ 1 ≤ k₂ ∧ k₂ < ℓ ∧
          (A s k₁ = B s k₁ ∨ (A s k₂ ≠ A s k₁ ∧ A s k₂ ≠ B s k₁) ∨
            (B s k₂ ≠ A s k₁ ∧ B s k₂ ≠ B s k₁)))
      have hmaj : ∀ s, ¬ Good s → ℓ ≤ F (μ s) ∨
          ∃ b, A s 1 ≠ b ∧ μ s ≠ A s 1 ∧ μ s ≠ b ∧ ℓ - 1 ≤ F (A s 1) ∧ ℓ - 1 ≤ F b := by
        intro s hng
        rw [not_and_or] at hng
        rcases hng with hnA | hnB
        · left
          have := hcount s (μ s) 0 (by
            intro k _ hk
            by_cases hk0 : k = 0
            · subst hk0
              left
              exact hA0 s
            · by_contra hcon
              push_neg at hcon
              exact hnA ⟨k, by omega, hk, by rw [hA0]; exact Ne.symm hcon.1,
                by rw [hA0]; exact Ne.symm hcon.2⟩)
          simpa using this
        · have hmix : ∀ k, 1 ≤ k → k < ℓ → A s k ≠ B s k :=
            fun k h1 h2 h => hnB ⟨k, 1, h1, h2, le_refl _, by omega, Or.inl h⟩
          have hinA : ∀ k, 1 ≤ k → k < ℓ → A s k = A s 1 ∨ A s k = B s 1 := by
            intro k h1 h2
            by_contra hc
            push_neg at hc
            exact hnB ⟨1, k, le_refl _, by omega, h1, h2, Or.inr (Or.inl hc)⟩
          have hinB : ∀ k, 1 ≤ k → k < ℓ → B s k = A s 1 ∨ B s k = B s 1 := by
            intro k h1 h2
            by_contra hc
            push_neg at hc
            exact hnB ⟨1, k, le_refl _, by omega, h1, h2, Or.inr (Or.inr hc)⟩
          have hcA : ∀ k, 1 ≤ k → k < ℓ → A s k = A s 1 ∨ B s k = A s 1 := by
            intro k h1 h2
            rcases hinA k h1 h2 with h | h
            · exact Or.inl h
            · rcases hinB k h1 h2 with h' | h'
              · exact Or.inr h'
              · exact absurd (h.trans h'.symm) (hmix k h1 h2)
          have hcB : ∀ k, 1 ≤ k → k < ℓ → A s k = B s 1 ∨ B s k = B s 1 := by
            intro k h1 h2
            rcases hinB k h1 h2 with h | h
            · rcases hinA k h1 h2 with h' | h'
              · exact absurd (h'.trans h.symm) (hmix k h1 h2)
              · exact Or.inl h'
            · exact Or.inr h
          have hFa := hcount s (A s 1) 1 hcA
          have hFb := hcount s (B s 1) 1 hcB
          by_cases hsa : μ s = A s 1
          · left
            have := hcount s (A s 1) 0 (by
              intro k _ hk
              by_cases hk0 : k = 0
              · subst hk0
                left
                rw [hA0]
                exact hsa
              · exact hcA k (by omega) hk)
            rw [hsa]
            simpa using this
          by_cases hsb : μ s = B s 1
          · left
            have := hcount s (B s 1) 0 (by
              intro k _ hk
              by_cases hk0 : k = 0
              · subst hk0
                right
                rw [hB0]
                exact hsb
              · exact hcB k (by omega) hk)
            rw [hsb]
            simpa using this
          right
          exact ⟨B s 1, hmix 1 le_rfl (by omega), hsa, hsb, hFa, hFb⟩
  13. There exists at least one base vertex s that is Good.

    Suppose for contradiction that no vertex is Good. Because the lists are not all identical, there exist vertices u, v with μ(u) ≠ μ(v). Since F(μ(u)) + F(μ(v)) ≤ 2ℓ - 1, at least one vertex s has F(μ(s)) < ℓ. Applying the classification of bad bases to s yields a color b distinct from μ(s) and A(s, 1) with F(A(s, 1)) ≥ ℓ - 1 and F(b) ≥ ℓ - 1. The three-color sum bound forces F(A(s, 1)) < ℓ. Setting t = s + 1 gives μ(t) = A(s, 1), so F(μ(t)) < ℓ. Applying the classification to t yields another color b' such that A(s, 1), A(t, 1), and b' are pairwise distinct with frequencies at least ℓ - 1. Their sum is at least 3(ℓ - 1) ≥ 2ℓ > 2ℓ - 1, contradicting the three-color sum bound.

    lines 385–416

      have hgood : ∃ s, Good s := by
        by_contra hno
        have hno' : ∀ s, ¬ Good s := fun s hs => hno ⟨s, hs⟩
        obtain ⟨u, v, huv⟩ := hne
        have hμuv : μ u ≠ μ v := by
          intro h
          apply huv
          rw [hμL u, hμL v, h]
        obtain ⟨s, hs⟩ : ∃ s, F (μ s) < ℓ := by
          by_contra hc
          push_neg at hc
          have := hsum2 _ _ hμuv
          have := hc u
          have := hc v
          omega
        rcases hmaj s (hno' s) with h | ⟨b, hab, hsa, hsb, hFa, hFb⟩
        · omega
        · have hFa' : F (A s 1) < ℓ := by
            by_contra hc
            push_neg at hc
            have := hsum3 (μ s) (A s 1) b hsa hsb hab
            have := hF1 s
            omega
          obtain ⟨t, ht⟩ : ∃ t, t = s + ((2 * 1 - 1 : ℕ) : Fin (2 * ℓ - 1)) := ⟨_, rfl⟩
          have hAt : A s 1 = μ t := by rw [hA, ht]
          rcases hmaj t (hno' t) with h | ⟨b', hab', hta, htb, hFa'', hFb'⟩
          · rw [← hAt] at h
            omega
          · rw [← hAt] at hta htb
            have := hsum3 (A s 1) (A t 1) b' hta htb hab'
            omega
      obtain ⟨s, hsA, hsB⟩ := hgood
  14. The odd antihole complement(C_{2ℓ-1}) is L-colorable.

    With a Good base vertex s in hand, Hall's marriage condition holds, so odd_antihole_colorable_of_common_palette_hall provides an injective representative function f choosing a color from L(s + 2j - 1) ∩ L(s + 2j) for each class j. Applying odd_antihole_colorable_of_common_palette_color with f yields a proper list coloring of the antihole.

    lines 417–422

    uses odd_antihole_colorable_of_common_palette_hall, odd_antihole_colorable_of_common_palette_color

      obtain ⟨f, hf, hft⟩ := odd_antihole_colorable_of_common_palette_hall ℓ hℓ P hP (A s) (B s)
        (by rw [hA0, hB0]) hsA hsB
      apply odd_antihole_colorable_of_common_palette_color ℓ hℓ L s f hf
      intro j
      rw [hμL, hμL, ← hA, ← hB]
      exact hft j
Fin.cast_val_eq_self
Coercing an element of Fin n to ℕ and casting it back yields the original element.
Finset.mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both.
SimpleGraph.compl_adj
Two vertices are adjacent in the graph complement if and only if they are distinct and not adjacent in the graph.
SimpleGraph.cycleGraph_adj'
Two vertices in a cycle graph of size n are adjacent if and only if their cyclic difference is 1 in either direction.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Fin.sub_def
Subtraction in Fin n is computed via modulo arithmetic: a - b = ⟨(n - b + a) % n, ...⟩.
Nat.add_mod_right
Adding a multiple of the modulus does not change the remainder: (x + z) % z = x % z.
Nat.mod_eq_of_lt
If a natural number is strictly less than the modulus, taking the remainder leaves it unchanged.
Finset.all_card_le_biUnion_card_iff_exists_injective
Hall's Marriage Theorem: an indexed family of finite sets admits a system of distinct representatives (an injective choice function) if and only if every subcollection S satisfies |S| ≤ |⋃_{x ∈ S} t(x)|.
Finset.mem_erase
An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
Finset.pred_card_le_card_erase
Erasing any element from a finite set decreases its cardinality by at most 1.
Finset.card_le_card
If s ⊆ t for finite sets, then |s| ≤ |t|.
Finset.card_le_univ
The cardinality of any subset of a finite type is at most the cardinality of the full type.
Finset.subset_biUnion_of_mem
Each member set t(x) is a subset of the union ⋃_{i ∈ s} t(i) for any index x ∈ s.
Finset.eq_univ_of_card
A subset of a finite type with the same cardinality as the type is the entire universal set.
Finset.mem_biUnion
An element belongs to a union of sets if and only if it belongs to at least one set in the family.
Finset.mem_univ
Every element of a finite type belongs to Finset.univ.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s|, then s = t.
Finset.card_erase_of_mem
Erasing an element that belongs to s decreases the cardinality by exactly 1.
Finset.card_univ
The cardinality of Finset.univ is the cardinality of the underlying finite type.
Fintype.card_fin
The cardinality of Fin n is n.
Fin.ext_iff
Two elements of Fin n are equal if and only if their values in ℕ are equal.
Finset.mem_union_left
An element of s belongs to the union s ∪ t.
Finset.mem_union_right
An element of t belongs to the union s ∪ t.
Finset.union_subset
If both s ⊆ u and t ⊆ u, then s ∪ t ⊆ u.
add_left_cancel
In an additive structure, a + b = a + c implies b = c.
congrArg
If two inputs are equal, a function maps them to equal outputs.
Fin.val_cast_of_lt
The natural-number value of casting a < n into Fin n is a.
Finset.card_le_card_of_injOn
If a function maps s into t and is injective on s, then |s| ≤ |t|.
Finset.coe_Ico
The coercion of the half-open interval Finset.Ico a b to a set is Set.Ico a b.
Set.mem_Ico
Membership in Set.Ico a b is equivalent to a ≤ x and x < b.
Finset.coe_filter
The coercion of a filtered finset is the set of elements satisfying the filter condition.
true_and
The proposition True ∧ p is equivalent to p.
Set.mem_ofPred_eq
Membership in a set defined by a predicate equals the predicate holding on that element.
Or.resolve_right
If a ∨ b holds and b is false, then a holds.
Finset.disjoint_filter
Two filtered sub-finsets of a set are disjoint if and only if no element satisfies both conditions.
Finset.disjoint_union_left
A union s ∪ t is disjoint from u if and only if both s and t are disjoint from u.
Finset.card_union_of_disjoint
The cardinality of the union of disjoint finite sets is the sum of their cardinalities.
Finset.card_sdiff_of_subset
If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.card_eq_one
A finite set has cardinality 1 if and only if it is a singleton.
Finset.mem_singleton_self
An element belongs to its own singleton set.
Finset.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and not to t.
Finset.mem_singleton
An element b belongs to {a} if and only if b = a.
Finset.card_pos
A finite set has positive cardinality if and only if it is nonempty.
odd_antihole_colorable_of_common_palette_sum2
The sum of the sizes of any two distinct color classes is at most the total number of vertices n.
odd_antihole_colorable_of_common_palette_sum3
The sum of the sizes of any three pairwise distinct color classes is at most the total number of vertices n.
odd_antihole_colorable_of_common_palette_count
If every pairing class with index in [lo, ℓ) contains a vertex of color c, then at least ℓ - lo vertices have color c.
not_and_or
Negation of a conjunction is the disjunction of the negations: ¬(a ∧ b) ↔ ¬a ∨ ¬b.
Ne.symm
Inequality is symmetric: a ≠ b implies b ≠ a.
le_refl
Reflexivity of the preorder relation: a ≤ a.
Or.inl
Left disjunction introduction: a implies a ∨ b.
Or.inr
Right disjunction introduction: b implies a ∨ b.
le_rfl
Reflexivity of inequality: a ≤ a.
odd_antihole_colorable_of_common_palette_hall
Under non-degeneracy conditions, Hall's condition holds for the pairing classes, yielding an injective color choice.
odd_antihole_colorable_of_common_palette_color
An injective choice function on the pairing classes yields a proper list coloring of the antihole.

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

Lean’s trace was cut to the first 400 of 419 tactics.

open Fin.NatCast in/-- Colouring from a system of distinct representatives of the classes`{s + (2j-1), s + 2j}`, `j < ℓ` (class `0` is the singleton `{s}`). -/theorem odd_antihole_colorable_of_common_palette_color (ℓ : ℕ) (hℓ : 3 ≤ ℓ)    [NeZero (2 * ℓ - 1)] (L : Fin (2 * ℓ - 1) → Finset ℕ) (s : Fin (2 * ℓ - 1))    (f : Fin ℓ → ℕ) (hf : Function.Injective f)    (hft : ∀ j : Fin ℓ, f j ∈ L (s + ((2 * j.val - 1 : ℕ) : Fin (2 * ℓ - 1))) ∩      L (s + ((2 * j.val : ℕ) : Fin (2 * ℓ - 1)))) :    ∃ c : Fin (2 * ℓ - 1) → ℕ, (∀ v, c v ∈ L v) ∧      ∀ u v, (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Adj u v → c u ≠ c v := by  have hcls : ∀ v : Fin (2 * ℓ - 1), ((v - s).val + 1) / 2 < ℓ := by    intro v    have := (v - s).isLt    omega  refine ⟨fun v => f ⟨((v - s).val + 1) / 2, hcls v⟩, ?_, ?_⟩  · intro v    have hv : s + (((v - s).val : ℕ) : Fin (2 * ℓ - 1)) = v := by      rw [Fin.cast_val_eq_self]      abel    have h := hft ⟨((v - s).val + 1) / 2, hcls v⟩    simp only [Finset.mem_inter] at h    have key : 2 * (((v - s).val + 1) / 2) - 1 = (v - s).val ∨        2 * (((v - s).val + 1) / 2) = (v - s).val := by omega    rcases key with k | k    · have h1 := h.1      rw [k, hv] at h1      exact h1    · have h2 := h.2      rw [k, hv] at h2      exact h2  · intro u v hadj heq    rw [SimpleGraph.compl_adj] at hadj    obtain ⟨hne, hnadj⟩ := hadj    apply hnadj    have heq' := Fin.mk.inj_iff.mp (hf heq)    rw [SimpleGraph.cycleGraph_adj']    have hij : (u - s).val ≠ (v - s).val := by      intro h      apply hne      have : u - s = v - s := Fin.ext h      simpa using this    have hsub : u - v = (u - s) - (v - s) := by abel    have hsub' : v - u = (v - s) - (u - s) := by abel    rw [hsub, hsub']    have hu := (u - s).isLt    have hv := (v - s).isLt    rcases (show (u - s).val = (v - s).val + 1 ∨ (v - s).val = (u - s).val + 1 by omega) with h | h    · left      rw [Fin.sub_def]      simp only      rw [h, show 2 * ℓ - 1 - (v - s).val + ((v - s).val + 1) = 1 + (2 * ℓ - 1) by omega,        Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)]    · right      rw [Fin.sub_def]      simp only      rw [h, show 2 * ℓ - 1 - (u - s).val + ((u - s).val + 1) = 1 + (2 * ℓ - 1) by omega,        Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)]/-- Hall's condition for the classes of one pairing. -/theorem odd_antihole_colorable_of_common_palette_hall (ℓ : ℕ) (hℓ : 3 ≤ ℓ) (P : Finset ℕ)    (hP : P.card = ℓ) (a b : ℕ → ℕ) (h0 : a 0 = b 0)    (hA : ∃ k, 1 ≤ k ∧ k < ℓ ∧ a 0 ≠ a k ∧ a 0 ≠ b k)    (hB : ∃ k₁ k₂, 1 ≤ k₁ ∧ k₁ < ℓ ∧ 1 ≤ k₂ ∧ k₂ < ℓ ∧      (a k₁ = b k₁ ∨ (a k₂ ≠ a k₁ ∧ a k₂ ≠ b k₁) ∨ (b k₂ ≠ a k₁ ∧ b k₂ ≠ b k₁))) :    ∃ f : Fin ℓ → ℕ, Function.Injective f ∧      ∀ j : Fin ℓ, f j ∈ P.erase (a j.val) ∩ P.erase (b j.val) := by  classical  set t : Fin ℓ → Finset ℕ := fun j => P.erase (a j.val) ∩ P.erase (b j.val) with ht_def  apply (Finset.all_card_le_biUnion_card_iff_exists_injective t).mp  have ht : ∀ j, ℓ - 2 ≤ (t j).card := by    intro j    have h1 : (P.erase (a j.val)).erase (b j.val) ⊆ t j := by      intro x hx      simp only [Finset.mem_erase] at hx      simp only [ht_def, Finset.mem_inter, Finset.mem_erase]      tauto    have h2 := Finset.pred_card_le_card_erase (s := P.erase (a j.val)) (a := b j.val)    have h3 := Finset.pred_card_le_card_erase (s := P) (a := a j.val)    have h4 := Finset.card_le_card h1    omega  have ht0 : ℓ - 1 ≤ (t ⟨0, by omega⟩).card := by    have hsub : P.erase (a 0) ⊆ t ⟨0, by omega⟩ := by      intro x hx      simp only [ht_def, Finset.mem_inter]      exact ⟨hx, by rw [← h0]; exact hx⟩    have := Finset.card_le_card hsub    have := Finset.pred_card_le_card_erase (s := P) (a := a 0)    omega  intro S  have hSle : S.card ≤ ℓ := by simpa using Finset.card_le_univ S  by_cases hS : S.card ≤ ℓ - 2  · rcases S.eq_empty_or_nonempty with rfl | ⟨j, hj⟩    · simp    · exact hS.trans ((ht j).trans (Finset.card_le_card (Finset.subset_biUnion_of_mem t hj)))  by_cases h0S : (⟨0, by omega⟩ : Fin ℓ) ∈ S  · by_cases hSf : S.card = ℓ    · have hSu : S = Finset.univ := Finset.eq_univ_of_card S (by simpa using hSf)      have hPsub : P ⊆ S.biUnion t := by        intro x hx        rw [Finset.mem_biUnion]        by_cases hx0 : x = a 0        · obtain ⟨k, hk1, hk2, hak, hbk⟩ := hA          refine ⟨⟨k, hk2⟩, by rw [hSu]; exact Finset.mem_univ _, ?_⟩          simp only [ht_def, Finset.mem_inter, Finset.mem_erase]          rw [hx0] at hx ⊢          exact ⟨⟨hak, hx⟩, ⟨hbk, hx⟩⟩        · refine ⟨⟨0, by omega⟩, h0S, ?_⟩          simp only [ht_def, Finset.mem_inter, Finset.mem_erase]          exact ⟨⟨hx0, hx⟩, ⟨by rw [← h0]; exact hx0, hx⟩⟩      calc S.card = ℓ := hSf        _ = P.card := hP.symm        _ ≤ _ := Finset.card_le_card hPsub    · have : S.card ≤ ℓ - 1 := by omega      exact this.trans (ht0.trans (Finset.card_le_card (Finset.subset_biUnion_of_mem t h0S)))  · obtain ⟨k₁, k₂, hk1, hk1', hk2, hk2', hcase⟩ := hB    have hSsub : S ⊆ Finset.univ.erase ⟨0, by omega⟩ := by      intro j hj      rw [Finset.mem_erase]      exact ⟨fun h => h0S (h ▸ hj), Finset.mem_univ _⟩    have hSeq : S = Finset.univ.erase ⟨0, by omega⟩ := by      apply Finset.eq_of_subset_of_card_le hSsub      rw [Finset.card_erase_of_mem (Finset.mem_univ _)]      simp only [Finset.card_univ, Fintype.card_fin]      omega    have hm1 : (⟨k₁, hk1'⟩ : Fin ℓ) ∈ S := by      rw [hSeq, Finset.mem_erase]      refine ⟨?_, Finset.mem_univ _⟩      intro h      simp only [Fin.ext_iff] at h      omega    have hm2 : (⟨k₂, hk2'⟩ : Fin ℓ) ∈ S := by      rw [hSeq, Finset.mem_erase]      refine ⟨?_, Finset.mem_univ _⟩      intro h      simp only [Fin.ext_iff] at h      omega    have hsub1 := Finset.subset_biUnion_of_mem t hm1    have hsub2 := Finset.subset_biUnion_of_mem t hm2    have key : ∃ m, P.erase m ⊆ t ⟨k₁, hk1'⟩ ∪ t ⟨k₂, hk2'⟩ := by      rcases hcase with h | ⟨h1, h2⟩ | ⟨h1, h2⟩      · refine ⟨a k₁, ?_⟩        intro x hx        apply Finset.mem_union_left        simp only [Finset.mem_erase] at hx        simp only [ht_def, Finset.mem_inter, Finset.mem_erase]        exact ⟨hx, ⟨by rw [← h]; exact hx.1, hx.2⟩⟩      · refine ⟨b k₂, ?_⟩        intro x hx        simp only [Finset.mem_erase] at hx        by_cases hxa : x = a k₂        · apply Finset.mem_union_left          simp only [ht_def, Finset.mem_inter, Finset.mem_erase]          rw [hxa] at hx ⊢          exact ⟨⟨h1, hx.2⟩, ⟨h2, hx.2⟩⟩        · apply Finset.mem_union_right          simp only [ht_def, Finset.mem_inter, Finset.mem_erase]          exact ⟨⟨hxa, hx.2⟩, hx⟩      · refine ⟨a k₂, ?_⟩        intro x hx        simp only [Finset.mem_erase] at hx        by_cases hxb : x = b k₂        · apply Finset.mem_union_left          simp only [ht_def, Finset.mem_inter, Finset.mem_erase]          rw [hxb] at hx ⊢          exact ⟨⟨h1, hx.2⟩, ⟨h2, hx.2⟩⟩        · apply Finset.mem_union_right          simp only [ht_def, Finset.mem_inter, Finset.mem_erase]          exact ⟨hx, ⟨hxb, hx.2⟩⟩    obtain ⟨m, hm⟩ := key    have hScard : S.card = ℓ - 1 := by      rw [hSeq, Finset.card_erase_of_mem (Finset.mem_univ _)]      simp only [Finset.card_univ, Fintype.card_fin]    have := Finset.card_le_card (hm.trans (Finset.union_subset hsub1 hsub2))    have := Finset.pred_card_le_card_erase (s := P) (a := m)    omegaopen Fin.NatCast in/-- If every class of the pairing at `s` with index in `[lo, ℓ)` contains a vertex ofcolour `c`, then at least `ℓ - lo` vertices have colour `c`. -/theorem odd_antihole_colorable_of_common_palette_count (ℓ : ℕ) (hℓ : 3 ≤ ℓ)    [NeZero (2 * ℓ - 1)] (μ : Fin (2 * ℓ - 1) → ℕ) (s : Fin (2 * ℓ - 1)) (c lo : ℕ)    (h : ∀ k, lo ≤ k → k < ℓ → μ (s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1))) = c ∨      μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) = c) :    ℓ - lo ≤ (Finset.univ.filter (fun v => μ v = c)).card := by  have hw : ∀ i j : ℕ, i < 2 * ℓ - 1 → j < 2 * ℓ - 1 →      s + ((i : ℕ) : Fin (2 * ℓ - 1)) = s + ((j : ℕ) : Fin (2 * ℓ - 1)) → i = j := by    intro i j hi hj hij    have h' := add_left_cancel hij    have := congrArg Fin.val h'    rwa [Fin.val_cast_of_lt hi, Fin.val_cast_of_lt hj] at this  let g : ℕ → Fin (2 * ℓ - 1) := fun k =>    if μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) = c then s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))    else s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1))  have hle := Finset.card_le_card_of_injOn g (s := Finset.Ico lo ℓ)    (t := Finset.univ.filter (fun v => μ v = c)) ?_ ?_  · simpa using hle  · intro k hk    simp only [Finset.coe_Ico, Set.mem_Ico] at hk    simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq, g]    split_ifs with h1    · exact h1    · exact (h k hk.1 hk.2).resolve_right h1  · intro k1 hk1 k2 hk2 heq    simp only [Finset.coe_Ico, Set.mem_Ico] at hk1 hk2    simp only [g] at heq    split_ifs at heq <;> (have := hw _ _ (by omega) (by omega) heq; omega)/-- Three distinct colour classes have at most `n` vertices together. -/theorem odd_antihole_colorable_of_common_palette_sum3 {n : ℕ} (μ : Fin n → ℕ) (a b c : ℕ)    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :    (Finset.univ.filter (fun v => μ v = a)).card + (Finset.univ.filter (fun v => μ v = b)).card      + (Finset.univ.filter (fun v => μ v = c)).card ≤ n := by  have d1 : Disjoint (Finset.univ.filter (fun v => μ v = a))      (Finset.univ.filter (fun v => μ v = b)) := by    rw [Finset.disjoint_filter]    intro x _ h1 h2    exact hab (h1.symm.trans h2)  have d2 : Disjoint (Finset.univ.filter (fun v => μ v = a) ∪      Finset.univ.filter (fun v => μ v = b)) (Finset.univ.filter (fun v => μ v = c)) := by    rw [Finset.disjoint_union_left]    constructor    · rw [Finset.disjoint_filter]      intro x _ h1 h2      exact hac (h1.symm.trans h2)    · rw [Finset.disjoint_filter]      intro x _ h1 h2      exact hbc (h1.symm.trans h2)  have e1 := Finset.card_union_of_disjoint d1  have e2 := Finset.card_union_of_disjoint d2  have e3 := Finset.card_le_univ (Finset.univ.filter (fun v => μ v = a) ∪      Finset.univ.filter (fun v => μ v = b) ∪ Finset.univ.filter (fun v => μ v = c))  rw [Fintype.card_fin] at e3  omega/-- Two distinct colour classes have at most `n` vertices together. -/theorem odd_antihole_colorable_of_common_palette_sum2 {n : ℕ} (μ : Fin n → ℕ) (a b : ℕ)    (hab : a ≠ b) :    (Finset.univ.filter (fun v => μ v = a)).card +      (Finset.univ.filter (fun v => μ v = b)).card ≤ n := by  have d1 : Disjoint (Finset.univ.filter (fun v => μ v = a))      (Finset.univ.filter (fun v => μ v = b)) := by    rw [Finset.disjoint_filter]    intro x _ h1 h2    exact hab (h1.symm.trans h2)  have e1 := Finset.card_union_of_disjoint d1  have e3 := Finset.card_le_univ (Finset.univ.filter (fun v => μ v = a) ∪      Finset.univ.filter (fun v => μ v = b))  rw [Fintype.card_fin] at e3  omegatheorem odd_antihole_colorable_of_common_palette (ℓ : ℕ) (hℓ : 3 ≤ ℓ) (P : Finset ℕ)    (hP : P.card = ℓ) (L : Fin (2 * ℓ - 1) → Finset ℕ) (hL : ∀ v, (L v).card = ℓ - 1)    (hLP : ∀ v, L v ⊆ P) (hne : ∃ u v, L u ≠ L v) :    ∃ c : Fin (2 * ℓ - 1) → ℕ, (∀ v, c v ∈ L v) ∧      ∀ u v, (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Adj u v → c u ≠ c v := by  classical  have : NeZero (2 * ℓ - 1) := ⟨by omega⟩  letI : NatCast (Fin (2 * ℓ - 1)) := Fin.NatCast.instNatCast (2 * ℓ - 1)  -- each list is the palette minus one colour `μ v`  have hμ : ∀ v, ∃ m, m ∈ P ∧ L v = P.erase m := by    intro v    have hc : (P \ L v).card = 1 := by      rw [Finset.card_sdiff_of_subset (hLP v), hP, hL]      omega    obtain ⟨m, hm⟩ := Finset.card_eq_one.mp hc    have hmP : m ∈ P ∧ m ∉ L v := by      have : m ∈ P \ L v := by rw [hm]; exact Finset.mem_singleton_self m      exact Finset.mem_sdiff.mp this    refine ⟨m, hmP.1, ?_⟩    ext x    rw [Finset.mem_erase]    constructor    · intro hx      exact ⟨fun h => hmP.2 (h ▸ hx), hLP v hx⟩    · rintro ⟨hxm, hxP⟩      by_contra hxL      have : x ∈ P \ L v := Finset.mem_sdiff.mpr ⟨hxP, hxL⟩      rw [hm, Finset.mem_singleton] at this      exact hxm this  choose μ _ hμL using hμ  obtain ⟨F, hF⟩ : ∃ F : ℕ → ℕ, ∀ c, F c = (Finset.univ.filter (fun v => μ v = c)).card :=    ⟨_, fun _ => rfl⟩  obtain ⟨A, hA⟩ : ∃ A : Fin (2 * ℓ - 1) → ℕ → ℕ,      ∀ s k, A s k = μ (s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1))) := ⟨_, fun _ _ => rfl⟩  obtain ⟨B, hB⟩ : ∃ B : Fin (2 * ℓ - 1) → ℕ → ℕ,      ∀ s k, B s k = μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) := ⟨_, fun _ _ => rfl⟩  have hA0 : ∀ s, A s 0 = μ s := fun s => by rw [hA]; simp  have hB0 : ∀ s, B s 0 = μ s := fun s => by rw [hB]; simp  have hF1 : ∀ v, 1 ≤ F (μ v) := by    intro v    rw [hF]    exact Finset.card_pos.mpr ⟨v, by simp⟩  have hsum2 : ∀ a b, a ≠ b → F a + F b ≤ 2 * ℓ - 1 := by    intro a b h    rw [hF, hF]    exact odd_antihole_colorable_of_common_palette_sum2 μ a b h  have hsum3 : ∀ a b c, a ≠ b → a ≠ c → b ≠ c → F a + F b + F c ≤ 2 * ℓ - 1 := by    intro a b c h1 h2 h3    rw [hF, hF, hF]    exact odd_antihole_colorable_of_common_palette_sum3 μ a b c h1 h2 h3  have hcount : ∀ s c lo, (∀ k, lo ≤ k → k < ℓ → A s k = c ∨ B s k = c) → ℓ - lo ≤ F c := by    intro s c lo h    rw [hF]    apply odd_antihole_colorable_of_common_palette_count ℓ hℓ μ s c lo    intro k h1 h2    rw [← hA, ← hB]    exact h k h1 h2  -- a pairing is good when Hall's condition holds for it  let Good : Fin (2 * ℓ - 1) → Prop := fun s =>    (∃ k, 1 ≤ k ∧ k < ℓ ∧ A s 0 ≠ A s k ∧ A s 0 ≠ B s k) ∧    (∃ k₁ k₂, 1 ≤ k₁ ∧ k₁ < ℓ ∧ 1 ≤ k₂ ∧ k₂ < ℓ ∧      (A s k₁ = B s k₁ ∨ (A s k₂ ≠ A s k₁ ∧ A s k₂ ≠ B s k₁) ∨        (B s k₂ ≠ A s k₁ ∧ B s k₂ ≠ B s k₁)))  have hmaj : ∀ s, ¬ Good s → ℓ ≤ F (μ s) ∨      ∃ b, A s 1 ≠ b ∧ μ s ≠ A s 1 ∧ μ s ≠ b ∧ ℓ - 1 ≤ F (A s 1) ∧ ℓ - 1 ≤ F b := by    intro s hng    rw [not_and_or] at hng    rcases hng with hnA | hnB    · left      have := hcount s (μ s) 0 (by        intro k _ hk        by_cases hk0 : k = 0        · subst hk0          left          exact hA0 s        · by_contra hcon          push_neg at hcon          exact hnA ⟨k, by omega, hk, by rw [hA0]; exact Ne.symm hcon.1,            by rw [hA0]; exact Ne.symm hcon.2⟩)      simpa using this    · have hmix : ∀ k, 1 ≤ k → k < ℓ → A s k ≠ B s k :=        fun k h1 h2 h => hnB ⟨k, 1, h1, h2, le_refl _, by omega, Or.inl h⟩      have hinA : ∀ k, 1 ≤ k → k < ℓ → A s k = A s 1 ∨ A s k = B s 1 := by        intro k h1 h2        by_contra hc        push_neg at hc        exact hnB ⟨1, k, le_refl _, by omega, h1, h2, Or.inr (Or.inl hc)⟩      have hinB : ∀ k, 1 ≤ k → k < ℓ → B s k = A s 1 ∨ B s k = B s 1 := by        intro k h1 h2        by_contra hc        push_neg at hc        exact hnB ⟨1, k, le_refl _, by omega, h1, h2, Or.inr (Or.inr hc)⟩      have hcA : ∀ k, 1 ≤ k → k < ℓ → A s k = A s 1 ∨ B s k = A s 1 := by        intro k h1 h2        rcases hinA k h1 h2 with h | h        · exact Or.inl h        · rcases hinB k h1 h2 with h' | h'          · exact Or.inr h'          · exact absurd (h.trans h'.symm) (hmix k h1 h2)      have hcB : ∀ k, 1 ≤ k → k < ℓ → A s k = B s 1 ∨ B s k = B s 1 := by        intro k h1 h2        rcases hinB k h1 h2 with h | h        · rcases hinA k h1 h2 with h' | h'          · exact absurd (h'.trans h.symm) (hmix k h1 h2)          · exact Or.inl h'        · exact Or.inr h      have hFa := hcount s (A s 1) 1 hcA      have hFb := hcount s (B s 1) 1 hcB      by_cases hsa : μ s = A s 1      · left        have := hcount s (A s 1) 0 (by          intro k _ hk          by_cases hk0 : k = 0          · subst hk0            left            rw [hA0]            exact hsa          · exact hcA k (by omega) hk)        rw [hsa]        simpa using this      by_cases hsb : μ s = B s 1      · left        have := hcount s (B s 1) 0 (by          intro k _ hk          by_cases hk0 : k = 0          · subst hk0            right            rw [hB0]            exact hsb          · exact hcB k (by omega) hk)        rw [hsb]        simpa using this      right      exact ⟨B s 1, hmix 1 le_rfl (by omega), hsa, hsb, hFa, hFb⟩  have hgood : ∃ s, Good s := by    by_contra hno    have hno' : ∀ s, ¬ Good s := fun s hs => hno ⟨s, hs⟩    obtain ⟨u, v, huv⟩ := hne    have hμuv : μ u ≠ μ v := by      intro h      apply huv      rw [hμL u, hμL v, h]    obtain ⟨s, hs⟩ : ∃ s, F (μ s) < ℓ := by      by_contra hc      push_neg at hc      have := hsum2 _ _ hμuv      have := hc u      have := hc v      omega    rcases hmaj s (hno' s) with h | ⟨b, hab, hsa, hsb, hFa, hFb⟩    · omega    · have hFa' : F (A s 1) < ℓ := by        by_contra hc        push_neg at hc        have := hsum3 (μ s) (A s 1) b hsa hsb hab        have := hF1 s        omega      obtain ⟨t, ht⟩ : ∃ t, t = s + ((2 * 1 - 1 : ℕ) : Fin (2 * ℓ - 1)) := ⟨_, rfl⟩      have hAt : A s 1 = μ t := by rw [hA, ht]      rcases hmaj t (hno' t) with h | ⟨b', hab', hta, htb, hFa'', hFb'⟩      · rw [← hAt] at h        omega      · rw [← hAt] at hta htb        have := hsum3 (A s 1) (A t 1) b' hta htb hab'        omega  obtain ⟨s, hsA, hsB⟩ := hgood  obtain ⟨f, hf, hft⟩ := odd_antihole_colorable_of_common_palette_hall ℓ hℓ P hP (A s) (B s)    (by rw [hA0, hB0]) hsA hsB  apply odd_antihole_colorable_of_common_palette_color ℓ hℓ L s f hf  intro j  rw [hμL, hμL, ← hA, ← hB]  exact hft j
See it in the graphDiscuss this resultChallenge it