AFTD Auto-Formalizing Theoretical Domains

finite_rook_four_sparse_pattern

theoremverified

Let B be a set of at most seven cells in four rows, with every row occupied. If every cell of B has at least three other cells of B in its row or column, then some column contains all four rows; outside that column there are either no cells, or exactly three cells sharing a row or sharing a column.

Statement

theorem finite_rook_four_sparse_pattern {C : Type*} [DecidableEq C] (B : Finset (Fin 4 × C)) (hrows : ∀ r : Fin 4, ∃ c : C, (r,c) ∈ B) (hsize : B.card ≤ 7) (hneighbors : ∀ p ∈ B, 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card) : ∃ c : C, (∀ r : Fin 4, (r,c) ∈ B) ∧ (let E := B.filter fun p => p.2 ≠ c; E.card = 0 ∨ (E.card = 3 ∧ ((∃ r : Fin 4, ∀ p ∈ E, p.1 = r) ∨ (∃ d : C, ∀ p ∈ E, p.2 = d))))
Source
Rook-graph reduction for the 55-point colored fiber case of OP-1027, supported by experiment 27569.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • finite_rook_sparse_full_columnLet B be a finite set of cells with m possible rows. Suppose every row is occupied, B has fewer than 2m cells, and every selected cell has…

The proof, explained

By the companion theorem `finite_rook_sparse_full_column`, the conditions that |B| ≤ 7 < 2 · 4 and every cell has at least 3 rook-neighbors imply that some column c of B is entirely full (contains cells in all 4 rows). The set E of cells outside column c therefore has size at most 7 - 4 = 3. Each cell in E can have at most one rook-neighbor in column c (sharing its row), so it must have at least 3 - 1 = 2 rook-neighbors within E. If E is non-empty, this degree condition forces |E| ≥ 3, whence |E| = 3 and all three cells must be pairwise rook-aligned. Finally, an auxiliary lemma shows that any three pairwise rook-aligned cells in a grid must either all lie in the same row or all lie in the same column.

  1. Any three pairwise distinct, pairwise rook-aligned cells in Fin 4 × C all share a common row or all share a common column.

    We prove the auxiliary lemma `finite_rook_four_sparse_pattern_three_cells`. Let p, q, r be pairwise distinct cells such that each pair shares a row or a column. We case-split on whether p and q share a row (p.1 = q.1): if they do, and r also shares this row, all three share row p.1; if r does not share this row, then p and r must share a column (p.2 = r.2), and since q and r cannot share a row without contradicting p.1 ≠ r.1, q and r share a column (q.2 = r.2), so all three share column p.2. If instead p and q do not share a row, they must share a column (p.2 = q.2); then either r also shares this column, so all three share column p.2, or p and r share a row, in which case q and r can neither share a row nor a column, giving a contradiction in both branches. Hence, the three cells either all share a row or all share a column.

    lines 1–19

    private lemma finite_rook_four_sparse_pattern_three_cells {C : Type*} [DecidableEq C] {p q r : Fin 4 × C}
        (hpq : p ≠ q) (hpr : p ≠ r) (hqr : q ≠ r)
        (h1 : p.1 = q.1 ∨ p.2 = q.2) (h2 : p.1 = r.1 ∨ p.2 = r.2) (h3 : q.1 = r.1 ∨ q.2 = r.2) :
        (∃ a, p.1 = a ∧ q.1 = a ∧ r.1 = a) ∨ (∃ b, p.2 = b ∧ q.2 = b ∧ r.2 = b) := by
      by_cases hp : p.1 = q.1
      · by_cases hpr1 : p.1 = r.1
        · left; exact ⟨p.1, rfl, hp.symm, hpr1.symm⟩
        · have h2' : p.2 = r.2 := by rcases h2 with h | h; exact absurd h hpr1; exact h
          rcases h3 with h3 | h3
          · exact absurd (hp.trans h3) hpr1
          · right; exact ⟨p.2, rfl, h3.trans h2'.symm, h2'.symm⟩
      · have h1' : p.2 = q.2 := by rcases h1 with h | h; exact absurd h hp; exact h
        by_cases hpr2 : p.2 = r.2
        · right; exact ⟨p.2, rfl, h1'.symm, hpr2.symm⟩
        · have h2' : p.1 = r.1 := by rcases h2 with h | h; exact h; exact absurd h hpr2
          rcases h3 with h3 | h3
          · exact absurd (h2'.trans h3.symm) hp
          · exact absurd (h1'.trans h3) hpr2
    
  2. There exists a column c containing cells in all four rows of B.

    We apply the theorem `finite_rook_sparse_full_column` with m = 4. Since every row is occupied, |B| ≤ 7 < 2 · 4 = 8, and every cell in B has at least 3 rook-neighbors in B, all conditions of the theorem hold. This produces a column c ∈ C such that (r, c) ∈ B for every row r ∈ Fin 4. We witness c and the fullness hypothesis hc for the main existential statement.

    lines 20–23

    uses finite_rook_sparse_full_column

    theorem finite_rook_four_sparse_pattern {C : Type*} [DecidableEq C] (B : Finset (Fin 4 × C)) (hrows : ∀ r : Fin 4, ∃ c : C, (r,c) ∈ B) (hsize : B.card ≤ 7) (hneighbors : ∀ p ∈ B, 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card) : ∃ c : C, (∀ r : Fin 4, (r,c) ∈ B) ∧ (let E := B.filter fun p => p.2 ≠ c; E.card = 0 ∨ (E.card = 3 ∧ ((∃ r : Fin 4, ∀ p ∈ E, p.1 = r) ∨ (∃ d : C, ∀ p ∈ E, p.2 = d)))) := by
      obtain ⟨c, hc⟩ := finite_rook_sparse_full_column 4 B hrows (by omega) hneighbors
      refine ⟨c, hc, ?_⟩
      dsimp only
  3. The set E of cells in B outside column c has cardinality at most 3.

    Let S = {(r, c) | r ∈ Fin 4} be the cells in column c. Because the row coordinate is injective, |S| = |Fin 4| = 4 by `Finset.card_image_of_injective` and `Finset.card_univ`. Since column c is full, S ⊆ B. The set E = {p ∈ B | p.2 ≠ c} consists of all cells of B outside column c, so E ⊆ B \ S. By `Finset.card_sdiff` and `Finset.inter_eq_left.mpr`, |B \ S| = |B| - |S| ≤ 7 - 4 = 3. Thus |E| ≤ 3 by `Finset.card_le_card`.

    lines 24–51

    uses Finset.card_image_of_injective, Finset.card_univ, Finset.card_le_card, Finset.card_sdiff, Finset.inter_eq_left.mpr

      set E := B.filter (fun p => p.2 ≠ c) with hE
      set S : Finset (Fin 4 × C) := Finset.univ.image (fun r : Fin 4 => (r, c)) with hS
      have hScard : S.card = 4 := by
        rw [hS, Finset.card_image_of_injective _ (fun a b h => congrArg Prod.fst h), Finset.card_univ]
        simp
      have hSsub : S ⊆ B := by
        intro x hx
        rw [hS] at hx
        simp only [Finset.mem_image, Finset.mem_univ, true_and] at hx
        obtain ⟨r, rfl⟩ := hx
        exact hc r
      have hEsub : E ⊆ B \ S := by
        intro p hp
        rw [hE] at hp
        simp only [Finset.mem_filter] at hp
        refine Finset.mem_sdiff.mpr ⟨hp.1, ?_⟩
        intro hpS
        rw [hS] at hpS
        simp only [Finset.mem_image, Finset.mem_univ, true_and] at hpS
        obtain ⟨r, hr⟩ := hpS
        have : p.2 = c := by rw [← hr]
        exact hp.2 this
      have hEcard : E.card ≤ 3 := by
        have h1 : E.card ≤ (B \ S).card := Finset.card_le_card hEsub
        rw [Finset.card_sdiff] at h1
        have hinter : S ∩ B = S := Finset.inter_eq_left.mpr hSsub
        rw [hinter, hScard] at h1
        omega
  4. Every cell in E has at least 2 rook-neighbors in E.

    Let p ∈ E. Any rook-neighbor q ∈ B of p either has column coordinate c or does not. If q.2 = c, then since p.2 ≠ c, q cannot share its column with p; hence q must share its row with p (q.1 = p.1), which uniquely determines q as (p.1, c). If q.2 ≠ c, then q ∈ E, so q is a rook-neighbor of p within E. Thus the rook-neighbors of p in B are contained in {(p.1, c)} ∪ {q ∈ E | q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)}. Since p has at least 3 rook-neighbors in B, and inserting (p.1, c) increases the set size by at most 1 (by `Finset.card_insert_le`), p must have at least 3 - 1 = 2 rook-neighbors in E.

    lines 52–76

    uses Finset.card_le_card, Finset.card_insert_le

      have hsub : ∀ p ∈ E, (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) ⊆
          insert (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) := by
        intro p hpE q hq
        rw [Finset.mem_filter] at hq
        obtain ⟨hqB, hqne, hqrc⟩ := hq
        obtain ⟨hpB, hpc⟩ := Finset.mem_filter.mp (hE ▸ hpE)
        by_cases hqc : q.2 = c
        · have hqeq : q = (p.1, c) := by
            refine Prod.ext ?_ hqc
            rcases hqrc with h | h
            · exact h
            · exact absurd (h.symm.trans hqc) hpc
          rw [Finset.mem_insert]
          exact Or.inl hqeq
        · rw [Finset.mem_insert]
          exact Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨hqB, hqc⟩, hqne, hqrc⟩)
      have hN : ∀ p ∈ E, 2 ≤ (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := by
        intro p hpE
        obtain ⟨hpB, hpc⟩ := Finset.mem_filter.mp (hE ▸ hpE)
        have h1 : 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := hneighbors p hpB
        have h2 : (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤
            (insert (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2))).card :=
          Finset.card_le_card (hsub p hpE)
        have h3 := Finset.card_insert_le (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2))
        omega
  5. Either |E| = 0, or |E| = 3.

    The rook-neighbors of any cell a in E form a subset of E \ {a}. By `Nat.eq_zero_or_pos`, either |E| = 0, which immediately establishes the first disjunct of the theorem, or |E| > 0. If |E| > 0, by `Finset.card_pos.mp` there exists some cell p ∈ E. From the previous step, p has at least 2 rook-neighbors in E, all lying in E \ {p}. By `Finset.card_erase_of_mem`, |E \ {p}| = |E| - 1, so 2 ≤ |E| - 1 by `Finset.card_le_card`, which implies |E| ≥ 3. Together with |E| ≤ 3, this forces |E| = 3.

    lines 77–90

    uses Nat.eq_zero_or_pos, Finset.card_pos.mp, Finset.card_erase_of_mem, Finset.card_le_card

      have hsub2 : ∀ a, (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)) ⊆ E.erase a := by
        intro a q hq
        rw [Finset.mem_filter] at hq
        rw [Finset.mem_erase]
        exact ⟨hq.2.1, hq.1⟩
      rcases Nat.eq_zero_or_pos E.card with h0 | hpos
      · exact Or.inl h0
      · obtain ⟨p, hpE⟩ := Finset.card_pos.mp hpos
        have hNp : 2 ≤ (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := hN p hpE
        have hle : (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤ (E.erase p).card :=
          Finset.card_le_card (hsub2 p)
        have herase : (E.erase p).card = E.card - 1 := Finset.card_erase_of_mem hpE
        have hE3 : E.card = 3 := by omega
        refine Or.inr ⟨hE3, ?_⟩
  6. When |E| = 3, write E = {x, y, z}; then x, y, z are pairwise distinct and pairwise rook-aligned.

    Since |E| = 3, by `Finset.card_eq_three.mp` we can write E = {x, y, z} with x, y, z pairwise distinct. For each cell a ∈ E, its rook-neighbors in E are a subset of E \ {a}. Since a has at least 2 rook-neighbors in E and |E \ {a}| = 3 - 1 = 2 by `Finset.card_erase_of_mem`, the subset has the same cardinality as E \ {a}. By `Finset.eq_of_subset_of_card_le`, the rook-neighbors of a in E are all of E \ {a}. Thus every other cell b ∈ E (b ≠ a) is a rook-neighbor of a, meaning a and b share a row or share a column.

    lines 91–107

    uses Finset.card_eq_three.mp, Finset.card_erase_of_mem, Finset.eq_of_subset_of_card_le

        obtain ⟨x, y, z, hxy, hxz, hyz, hExyz⟩ := Finset.card_eq_three.mp hE3
        have hxE : x ∈ E := by rw [hExyz]; simp
        have hyE : y ∈ E := by rw [hExyz]; simp
        have hzE : z ∈ E := by rw [hExyz]; simp
        have hpair : ∀ a ∈ E, ∀ b ∈ E, a ≠ b → (a.1 = b.1 ∨ a.2 = b.2) := by
          intro a haE b hbE hab
          have hNa : 2 ≤ (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)).card := hN a haE
          have heq : (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)) = E.erase a := by
            apply Finset.eq_of_subset_of_card_le (hsub2 a)
            rw [Finset.card_erase_of_mem haE]
            omega
          have hb : b ∈ E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2) := by
            rw [heq]
            exact Finset.mem_erase.mpr ⟨Ne.symm hab, hbE⟩
          rcases (Finset.mem_filter.mp hb).2.2 with h | h
          · exact Or.inl h.symm
          · exact Or.inr h.symm
  7. The three cells in E all share a row or all share a column.

    We invoke the helper lemma `finite_rook_four_sparse_pattern_three_cells` on the three pairwise distinct and pairwise rook-aligned cells x, y, z ∈ E. The lemma asserts that they either all share a common row coordinate a, or all share a common column coordinate b. Because E = {x, y, z}, every element of E is x, y, or z. In the first case, every cell in E has row coordinate a; in the second case, every cell in E has column coordinate b. This completes the second disjunct.

    lines 108–128

    uses finite_rook_four_sparse_pattern_three_cells

        have hcomb := finite_rook_four_sparse_pattern_three_cells hxy hxz hyz
          (hpair x hxE y hyE hxy) (hpair x hxE z hzE hxz) (hpair y hyE z hzE hyz)
        rcases hcomb with ⟨a, hxa, hya, hza⟩ | ⟨b, hxb, hyb, hzb⟩
        · left
          refine ⟨a, ?_⟩
          intro q hqE
          rw [hExyz] at hqE
          simp only [Finset.mem_insert, Finset.mem_singleton] at hqE
          rcases hqE with rfl | rfl | rfl
          · exact hxa
          · exact hya
          · exact hza
        · right
          refine ⟨b, ?_⟩
          intro q hqE
          rw [hExyz] at hqE
          simp only [Finset.mem_insert, Finset.mem_singleton] at hqE
          rcases hqE with rfl | rfl | rfl
          · exact hxb
          · exact hyb
          · exact hzb
finite_rook_sparse_full_column
In an m-row grid, if every row is occupied, |B| < 2m, and every cell has at least m - 1 rook-neighbors in B, then some column of B contains cells in all m rows.
Finset.card_image_of_injective
The image of a finite set under an injective map has the same cardinality as the original set.
Finset.card_univ
The cardinality of the universal finset `Finset.univ` of a finite type is the cardinality of that type.
Finset.card_le_card
If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_sdiff
The cardinality of the set difference t \ s equals |t| - |s ∩ t|.
Finset.inter_eq_left.mpr
If s ⊆ t, then s ∩ t = s.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1: |insert a s| ≤ |s| + 1.
Nat.eq_zero_or_pos
Every natural number is either 0 or strictly positive.
Finset.card_pos.mp
If a finite set has strictly positive cardinality, it is non-empty.
Finset.card_erase_of_mem
Removing an element that belongs to a finite set decreases its cardinality by 1: |s \ {a}| = |s| - 1.
Finset.card_eq_three.mp
A finite set has cardinality 3 if and only if it consists of three pairwise distinct elements {x, y, z}.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s|, then s = t.
finite_rook_four_sparse_pattern_three_cells
If three pairwise distinct cells in a 4-row grid pairwise share a row or share a column, then all three share a row or all three share a column.

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

private lemma finite_rook_four_sparse_pattern_three_cells {C : Type*} [DecidableEq C] {p q r : Fin 4 × C}    (hpq : p ≠ q) (hpr : p ≠ r) (hqr : q ≠ r)    (h1 : p.1 = q.1 ∨ p.2 = q.2) (h2 : p.1 = r.1 ∨ p.2 = r.2) (h3 : q.1 = r.1 ∨ q.2 = r.2) :    (∃ a, p.1 = a ∧ q.1 = a ∧ r.1 = a) ∨ (∃ b, p.2 = b ∧ q.2 = b ∧ r.2 = b) := by  by_cases hp : p.1 = q.1  · by_cases hpr1 : p.1 = r.1    · left; exact ⟨p.1, rfl, hp.symm, hpr1.symm⟩    · have h2' : p.2 = r.2 := by rcases h2 with h | h; exact absurd h hpr1; exact h      rcases h3 with h3 | h3      · exact absurd (hp.trans h3) hpr1      · right; exact ⟨p.2, rfl, h3.trans h2'.symm, h2'.symm⟩  · have h1' : p.2 = q.2 := by rcases h1 with h | h; exact absurd h hp; exact h    by_cases hpr2 : p.2 = r.2    · right; exact ⟨p.2, rfl, h1'.symm, hpr2.symm⟩    · have h2' : p.1 = r.1 := by rcases h2 with h | h; exact h; exact absurd h hpr2      rcases h3 with h3 | h3      · exact absurd (h2'.trans h3.symm) hp      · exact absurd (h1'.trans h3) hpr2theorem finite_rook_four_sparse_pattern {C : Type*} [DecidableEq C] (B : Finset (Fin 4 × C)) (hrows : ∀ r : Fin 4, ∃ c : C, (r,c) ∈ B) (hsize : B.card ≤ 7) (hneighbors : ∀ p ∈ B, 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card) : ∃ c : C, (∀ r : Fin 4, (r,c) ∈ B) ∧ (let E := B.filter fun p => p.2 ≠ c; E.card = 0 ∨ (E.card = 3 ∧ ((∃ r : Fin 4, ∀ p ∈ E, p.1 = r) ∨ (∃ d : C, ∀ p ∈ E, p.2 = d)))) := by  obtain ⟨c, hc⟩ := finite_rook_sparse_full_column 4 B hrows (by omega) hneighbors  refine ⟨c, hc, ?_⟩  dsimp only  set E := B.filter (fun p => p.2 ≠ c) with hE  set S : Finset (Fin 4 × C) := Finset.univ.image (fun r : Fin 4 => (r, c)) with hS  have hScard : S.card = 4 := by    rw [hS, Finset.card_image_of_injective _ (fun a b h => congrArg Prod.fst h), Finset.card_univ]    simp  have hSsub : S ⊆ B := by    intro x hx    rw [hS] at hx    simp only [Finset.mem_image, Finset.mem_univ, true_and] at hx    obtain ⟨r, rfl⟩ := hx    exact hc r  have hEsub : E ⊆ B \ S := by    intro p hp    rw [hE] at hp    simp only [Finset.mem_filter] at hp    refine Finset.mem_sdiff.mpr ⟨hp.1, ?_⟩    intro hpS    rw [hS] at hpS    simp only [Finset.mem_image, Finset.mem_univ, true_and] at hpS    obtain ⟨r, hr⟩ := hpS    have : p.2 = c := by rw [← hr]    exact hp.2 this  have hEcard : E.card ≤ 3 := by    have h1 : E.card ≤ (B \ S).card := Finset.card_le_card hEsub    rw [Finset.card_sdiff] at h1    have hinter : S ∩ B = S := Finset.inter_eq_left.mpr hSsub    rw [hinter, hScard] at h1    omega  have hsub : ∀ p ∈ E, (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) ⊆      insert (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) := by    intro p hpE q hq    rw [Finset.mem_filter] at hq    obtain ⟨hqB, hqne, hqrc⟩ := hq    obtain ⟨hpB, hpc⟩ := Finset.mem_filter.mp (hE ▸ hpE)    by_cases hqc : q.2 = c    · have hqeq : q = (p.1, c) := by        refine Prod.ext ?_ hqc        rcases hqrc with h | h        · exact h        · exact absurd (h.symm.trans hqc) hpc      rw [Finset.mem_insert]      exact Or.inl hqeq    · rw [Finset.mem_insert]      exact Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨hqB, hqc⟩, hqne, hqrc⟩)  have hN : ∀ p ∈ E, 2 ≤ (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := by    intro p hpE    obtain ⟨hpB, hpc⟩ := Finset.mem_filter.mp (hE ▸ hpE)    have h1 : 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := hneighbors p hpB    have h2 : (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤        (insert (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2))).card :=      Finset.card_le_card (hsub p hpE)    have h3 := Finset.card_insert_le (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2))    omega  have hsub2 : ∀ a, (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)) ⊆ E.erase a := by    intro a q hq    rw [Finset.mem_filter] at hq    rw [Finset.mem_erase]    exact ⟨hq.2.1, hq.1⟩  rcases Nat.eq_zero_or_pos E.card with h0 | hpos  · exact Or.inl h0  · obtain ⟨p, hpE⟩ := Finset.card_pos.mp hpos    have hNp : 2 ≤ (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := hN p hpE    have hle : (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤ (E.erase p).card :=      Finset.card_le_card (hsub2 p)    have herase : (E.erase p).card = E.card - 1 := Finset.card_erase_of_mem hpE    have hE3 : E.card = 3 := by omega    refine Or.inr ⟨hE3, ?_⟩    obtain ⟨x, y, z, hxy, hxz, hyz, hExyz⟩ := Finset.card_eq_three.mp hE3    have hxE : x ∈ E := by rw [hExyz]; simp    have hyE : y ∈ E := by rw [hExyz]; simp    have hzE : z ∈ E := by rw [hExyz]; simp    have hpair : ∀ a ∈ E, ∀ b ∈ E, a ≠ b → (a.1 = b.1 ∨ a.2 = b.2) := by      intro a haE b hbE hab      have hNa : 2 ≤ (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)).card := hN a haE      have heq : (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)) = E.erase a := by        apply Finset.eq_of_subset_of_card_le (hsub2 a)        rw [Finset.card_erase_of_mem haE]        omega      have hb : b ∈ E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2) := by        rw [heq]        exact Finset.mem_erase.mpr ⟨Ne.symm hab, hbE⟩      rcases (Finset.mem_filter.mp hb).2.2 with h | h      · exact Or.inl h.symm      · exact Or.inr h.symm    have hcomb := finite_rook_four_sparse_pattern_three_cells hxy hxz hyz      (hpair x hxE y hyE hxy) (hpair x hxE z hzE hxz) (hpair y hyE z hzE hyz)    rcases hcomb with ⟨a, hxa, hya, hza⟩ | ⟨b, hxb, hyb, hzb⟩    · left      refine ⟨a, ?_⟩      intro q hqE      rw [hExyz] at hqE      simp only [Finset.mem_insert, Finset.mem_singleton] at hqE      rcases hqE with rfl | rfl | rfl      · exact hxa      · exact hya      · exact hza    · right      refine ⟨b, ?_⟩      intro q hqE      rw [hExyz] at hqE      simp only [Finset.mem_insert, Finset.mem_singleton] at hqE      rcases hqE with rfl | rfl | rfl      · exact hxb      · exact hyb      · exact hzb
See it in the graphDiscuss this resultChallenge it