blocking_card_three_of_three_crossing_points
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
- exists_triangle_through_three_points_avoidingFor three pairwise distinct points A, B, C in ℝ² and any finite family F of segments, there is a (possibly degenerate) triangle whose…
- segments_block_pointsA finite family of segments L blocks a finite point set P under the triangle-free crossing property if for every pair of distinct points…
- segment_crossing_graphThe crossing graph G(L) of a finite family of line segments L is the simple graph with vertex set L and edges between segments whose…
- not_cliqueFree_three_of_crosses_crossing_pair_tfIf L is a triangle-free segment family and a new segment uv crosses both segments of a crossing pair in L (distinct from both), then…
- segment_crossing_of_mem_openSegmentsIf a point x lies in the open segment uv and also in the open segment ab, then the segment uv crosses the segment ab.
- Used by 1
- triangle_free_blocking_ge_vertex_cover_of_le_threeFor every finite family of line segments L whose crossing graph is triangle-free and has vertex cover number at most 3, there exists a…
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.
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.
uses
Finset.mem_insert,Finset.mem_singletonsimp only [Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl <;> simp_all
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).
uses
Sym2.eq_iff,openSegment_symmhave hDuv : D ∈ openSegment ℝ u v := by rw [Sym2.eq_iff] at heq rcases heq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact hDp · rwa [openSegment_symm]
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.
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
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.
uses
not_cliqueFree_three_of_crosses_crossing_pair_tf,segment_crossing_of_mem_openSegmentsexact 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)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.
uses
exists_triangle_through_three_points_avoidingclassical 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 LThe 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.
uses
blocking_card_three_of_three_crossing_points_pair_cases,blocking_card_three_of_three_crossing_points_steprefine ⟨{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₂
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]