AFTD Auto-Formalizing Theoretical Domains

blocking_card_three_of_three_crossing_points

theoremverified

If A, B, C are three pairwise distinct points of the plane, each lying in the relative interiors of the two segments of one of three distinct crossing pairs of a triangle-free family L (with each pair's two segments distinct), then L blocks some three-element point set.

Statement

theorem blocking_card_three_of_three_crossing_points
    (L : Finset (Sym2 (ℝ × ℝ)))
    (h_tf : (segment_crossing_graph L).CliqueFree 3)
    (a₁ a₂ b₁ b₂ c₁ c₂ d₁ d₂ e₁ e₂ f₁ f₂ A B C : ℝ × ℝ)
    (ha : s(a₁, a₂) ∈ L) (hb : s(b₁, b₂) ∈ L) (hc : s(c₁, c₂) ∈ L)
    (hd : s(d₁, d₂) ∈ L) (he : s(e₁, e₂) ∈ L) (hf : s(f₁, f₂) ∈ L)
    (hab : s(a₁, a₂) ≠ s(b₁, b₂)) (hcd : s(c₁, c₂) ≠ s(d₁, d₂))
    (hef : s(e₁, e₂) ≠ s(f₁, f₂))
    (hA₁ : A ∈ openSegment ℝ a₁ a₂) (hA₂ : A ∈ openSegment ℝ b₁ b₂)
    (hB₁ : B ∈ openSegment ℝ c₁ c₂) (hB₂ : B ∈ openSegment ℝ d₁ d₂)
    (hC₁ : C ∈ openSegment ℝ e₁ e₂) (hC₂ : C ∈ openSegment ℝ f₁ f₂)
    (hAB : A ≠ B) (hBC : B ≠ C) (hCA : C ≠ A) :
    ∃ P : Finset (ℝ × ℝ), segments_block_points L P ∧ P.card = 3
Source
step towards triangle_free_blocking_ge_vertex_cover_of_le_three
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

The proof, explained

To show that the triangle-free segment family L blocks some 3-point set, we construct a triangle with vertices p₁, p₂, p₃ whose sides avoid L and contain the three crossing points A, B, C in their relative interiors. We set P = {p₁, p₂, p₃}, which has cardinality 3 because the vertices are pairwise distinct. Any two distinct vertices in P span one of the triangle's sides and thus pass through one of the crossing points, crossing the two segments of L that meet there; hence, adding that side to L creates a crossing triangle, showing that P is blocked.

  1. Any pair of distinct vertices from {p₁, p₂, p₃} forms one of the three segments s(p₁, p₂), s(p₂, p₃), or s(p₃, p₁).

    Unfolding membership in the three-element set using Finset.mem_insert and Finset.mem_singleton yields three possibilities for u and three for v. The cases where u = v contradict the hypothesis u ≠ v, and the remaining six combinations each reduce to one of the three unordered pairs by symmetry.

    lines 7–8

    uses Finset.mem_insert, Finset.mem_singleton

      simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv
      rcases hu with rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl <;> simp_all
  2. The crossing point D lies in the open segment between u and v.

    Since s(u, v) = s(p, q), Sym2.eq_iff gives either (u = p and v = q) or (u = q and v = p). In the first case, D ∈ openSegment ℝ u v is immediate from D ∈ openSegment ℝ p q; in the second case, it follows by the symmetry of open segments (openSegment_symm).

    lines 20–24

    uses Sym2.eq_iff, openSegment_symm

      have hDuv : D ∈ openSegment ℝ u v := by
        rw [Sym2.eq_iff] at heq
        rcases heq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩
        · exact hDp
        · rwa [openSegment_symm]
  3. The segment s(u, v) is distinct from both segments s(g₁, g₂) and s(h₁, h₂) in L.

    If s(u, v) were equal to either s(g₁, g₂) or s(h₁, h₂), then since s(u, v) = s(p, q), the segment s(p, q) would belong to L, contradicting the hypothesis that s(p, q) ∉ L.

    lines 25–34

      have hne1 : s(u, v) ≠ s(g₁, g₂) := by
        intro h
        apply hnotin
        rw [← heq, h]
        exact hg
      have hne2 : s(u, v) ≠ s(h₁, h₂) := by
        intro h
        apply hnotin
        rw [← heq, h]
        exact hh
  4. Adding s(u, v) to L creates a 3-clique in the crossing graph, so L ∪ {s(u, v)} is not triangle-free.

    Because D lies in the relative interiors of s(g₁, g₂), s(h₁, h₂), and s(u, v), all three segments mutually cross by segment_crossing_of_mem_openSegments. Since s(g₁, g₂) and s(h₁, h₂) are already distinct crossing segments in L, adding s(u, v) forms a crossing triangle by not_cliqueFree_three_of_crosses_crossing_pair_tf.

    lines 35–40

    uses not_cliqueFree_three_of_crosses_crossing_pair_tf, segment_crossing_of_mem_openSegments

      exact not_cliqueFree_three_of_crosses_crossing_pair_tf L h_tf
        (s(g₁, g₂)) (s(h₁, h₂)) hg hh hgh
        (segment_crossing_of_mem_openSegments g₁ g₂ h₁ h₂ D hDg hDh)
        u v hne1 hne2
        (segment_crossing_of_mem_openSegments u v g₁ g₂ D hDuv hDg)
        (segment_crossing_of_mem_openSegments u v h₁ h₂ D hDuv hDh)
  5. There exists a triangle with vertices p₁, p₂, p₃ whose open edges contain A, B, C and do not belong to L.

    Applying exists_triangle_through_three_points_avoiding to the pairwise distinct points A, B, C and the segment family L produces three distinct vertices p₁, p₂, p₃ such that A ∈ openSegment ℝ p₁ p₂, B ∈ openSegment ℝ p₂ p₃, and C ∈ openSegment ℝ p₃ p₁, with none of these three segments belonging to L.

    lines 56–58

    uses exists_triangle_through_three_points_avoiding

      classical
      obtain ⟨p₁, p₂, p₃, h12, h23, h31, hAp12, hBp23, hCp31, hn12, hn23, hn31⟩ :=
        exists_triangle_through_three_points_avoiding A B C hAB hBC hCA L
  6. The vertex set P = {p₁, p₂, p₃} is blocked by L.

    To show that L blocks P = {p₁, p₂, p₃}, take any distinct u, v ∈ P. By blocking_card_three_of_three_crossing_points_pair_cases, s(u, v) is one of the three sides s(p₁, p₂), s(p₂, p₃), or s(p₃, p₁). Each side contains one of the crossing points A, B, C in its interior, which is also the crossing point of a pair of distinct segments in L. Applying blocking_card_three_of_three_crossing_points_step to each case shows that inserting s(u, v) creates a 3-clique in the crossing graph.

    lines 59–68

    uses blocking_card_three_of_three_crossing_points_pair_cases, blocking_card_three_of_three_crossing_points_step

      refine ⟨{p₁, p₂, p₃}, ?_, ?_⟩
      · intro u v hu hv huv
        rcases blocking_card_three_of_three_crossing_points_pair_cases p₁ p₂ p₃ u v hu hv huv
          with h | h | h
        · exact blocking_card_three_of_three_crossing_points_step L h_tf u v
            a₁ a₂ b₁ b₂ A p₁ p₂ hn12 h hAp12 ha hb hab hA₁ hA₂
        · exact blocking_card_three_of_three_crossing_points_step L h_tf u v
            c₁ c₂ d₁ d₂ B p₂ p₃ hn23 h hBp23 hc hd hcd hB₁ hB₂
        · exact blocking_card_three_of_three_crossing_points_step L h_tf u v
            e₁ e₂ f₁ f₂ C p₃ p₁ hn31 h hCp31 he hf hef hC₁ hC₂
  7. The set P = {p₁, p₂, p₃} has cardinality 3.

    Because the vertices are pairwise distinct (p₁ ≠ p₂, p₂ ≠ p₃, and p₃ ≠ p₁, the last reversed by Ne.symm), the set contains exactly three points.

    line 69

    uses Ne.symm

      · simp [h12, h23, Ne.symm h31]
Finset.mem_insert
An element belongs to the insertion of b into a finite set s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to a singleton set {a} if and only if it equals a.
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if either (x = z and y = w) or (x = w and y = z).
openSegment_symm
The open segment between x and y is symmetric: openSegment ℝ x y = openSegment ℝ y x.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
not_cliqueFree_three_of_crosses_crossing_pair_tf
If L is a triangle-free segment family and a new segment crosses both segments of an already crossing pair in L, then adding the new segment creates a 3-clique in the crossing graph.
segment_crossing_of_mem_openSegments
If a point lies in the open segments of two segments, then the two segments cross.
exists_triangle_through_three_points_avoiding
Given three pairwise distinct points and a finite segment family, there exists a triangle whose open edges contain the three points and none of whose edges belong to the family.
blocking_card_three_of_three_crossing_points_pair_cases
Any pair of distinct elements chosen from a 3-element set {p₁, p₂, p₃} forms one of the three segments s(p₁, p₂), s(p₂, p₃), or s(p₃, p₁).
blocking_card_three_of_three_crossing_points_step
If an edge not in L shares an interior point with two distinct segments of L, adding that edge to L creates a 3-clique in the crossing graph.

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 blocking_card_three_of_three_crossing_points_pair_cases    (p₁ p₂ p₃ u v : ℝ × ℝ)    (hu : u ∈ ({p₁, p₂, p₃} : Finset (ℝ × ℝ)))    (hv : v ∈ ({p₁, p₂, p₃} : Finset (ℝ × ℝ)))    (huv : u ≠ v) :    s(u, v) = s(p₁, p₂) ∨ s(u, v) = s(p₂, p₃) ∨ s(u, v) = s(p₃, p₁) := by  simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv  rcases hu with rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl <;> simp_allprivate lemma blocking_card_three_of_three_crossing_points_step    (L : Finset (Sym2 (ℝ × ℝ)))    (h_tf : (segment_crossing_graph L).CliqueFree 3)    (u v g₁ g₂ h₁ h₂ D p q : ℝ × ℝ)    (hnotin : s(p, q) ∉ L)    (heq : s(u, v) = s(p, q))    (hDp : D ∈ openSegment ℝ p q)    (hg : s(g₁, g₂) ∈ L) (hh : s(h₁, h₂) ∈ L) (hgh : s(g₁, g₂) ≠ s(h₁, h₂))    (hDg : D ∈ openSegment ℝ g₁ g₂) (hDh : D ∈ openSegment ℝ h₁ h₂) :    ¬ (segment_crossing_graph (insert s(u, v) L)).CliqueFree 3 := by  have hDuv : D ∈ openSegment ℝ u v := by    rw [Sym2.eq_iff] at heq    rcases heq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩    · exact hDp    · rwa [openSegment_symm]  have hne1 : s(u, v) ≠ s(g₁, g₂) := by    intro h    apply hnotin    rw [← heq, h]    exact hg  have hne2 : s(u, v) ≠ s(h₁, h₂) := by    intro h    apply hnotin    rw [← heq, h]    exact hh  exact not_cliqueFree_three_of_crosses_crossing_pair_tf L h_tf    (s(g₁, g₂)) (s(h₁, h₂)) hg hh hgh    (segment_crossing_of_mem_openSegments g₁ g₂ h₁ h₂ D hDg hDh)    u v hne1 hne2    (segment_crossing_of_mem_openSegments u v g₁ g₂ D hDuv hDg)    (segment_crossing_of_mem_openSegments u v h₁ h₂ D hDuv hDh)/-- Three distinct interior crossing points of a triangle-free family yield a blocked 3-point set (sides of a triangle through A, B, C). -/theorem blocking_card_three_of_three_crossing_points    (L : Finset (Sym2 (ℝ × ℝ)))    (h_tf : (segment_crossing_graph L).CliqueFree 3)    (a₁ a₂ b₁ b₂ c₁ c₂ d₁ d₂ e₁ e₂ f₁ f₂ A B C : ℝ × ℝ)    (ha : s(a₁, a₂) ∈ L) (hb : s(b₁, b₂) ∈ L) (hc : s(c₁, c₂) ∈ L)    (hd : s(d₁, d₂) ∈ L) (he : s(e₁, e₂) ∈ L) (hf : s(f₁, f₂) ∈ L)    (hab : s(a₁, a₂) ≠ s(b₁, b₂)) (hcd : s(c₁, c₂) ≠ s(d₁, d₂))    (hef : s(e₁, e₂) ≠ s(f₁, f₂))    (hA₁ : A ∈ openSegment ℝ a₁ a₂) (hA₂ : A ∈ openSegment ℝ b₁ b₂)    (hB₁ : B ∈ openSegment ℝ c₁ c₂) (hB₂ : B ∈ openSegment ℝ d₁ d₂)    (hC₁ : C ∈ openSegment ℝ e₁ e₂) (hC₂ : C ∈ openSegment ℝ f₁ f₂)    (hAB : A ≠ B) (hBC : B ≠ C) (hCA : C ≠ A) :    ∃ P : Finset (ℝ × ℝ), segments_block_points L P ∧ P.card = 3 := by  classical  obtain ⟨p₁, p₂, p₃, h12, h23, h31, hAp12, hBp23, hCp31, hn12, hn23, hn31⟩ :=    exists_triangle_through_three_points_avoiding A B C hAB hBC hCA L  refine ⟨{p₁, p₂, p₃}, ?_, ?_⟩  · intro u v hu hv huv    rcases blocking_card_three_of_three_crossing_points_pair_cases p₁ p₂ p₃ u v hu hv huv      with h | h | h    · exact blocking_card_three_of_three_crossing_points_step L h_tf u v        a₁ a₂ b₁ b₂ A p₁ p₂ hn12 h hAp12 ha hb hab hA₁ hA₂    · exact blocking_card_three_of_three_crossing_points_step L h_tf u v        c₁ c₂ d₁ d₂ B p₂ p₃ hn23 h hBp23 hc hd hcd hB₁ hB₂    · exact blocking_card_three_of_three_crossing_points_step L h_tf u v        e₁ e₂ f₁ f₂ C p₃ p₁ hn31 h hCp31 he hf hef hC₁ hC₂  · simp [h12, h23, Ne.symm h31]
See it in the graphDiscuss this resultChallenge it