triangle_free_blocking_ge_vertex_cover_of_le_three
For every finite family of line segments L whose crossing graph is triangle-free and has vertex cover number at most 3, there exists a point set P blocked by L with cardinality at least the vertex cover number.
Statement
theorem triangle_free_blocking_ge_vertex_cover_of_le_three
(L : Finset (Sym2 (ℝ × ℝ)))
(h_tf : (segment_crossing_graph L).CliqueFree 3)
(h_vc : (segment_crossing_graph L).vertexCoverNum ≤ 3) :
∃ P : Finset (ℝ × ℝ), segments_block_points L P ∧
(segment_crossing_graph L).vertexCoverNum ≤ P.card- Source
- step towards triangle_free_blocking_ge_vertex_cover
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- triangle_midpoints_existFor any three pairwise distinct points A, B, C in ℝ², there exist three distinct points p₁, p₂, p₃ forming a triangle whose open sides…
- 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.
- 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…
- triangle_free_blocking_ge_vertex_cover_of_le_twoFor every finite family of line segments L whose crossing graph is triangle-free and has vertex cover number at most 2, there exists a…
- 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…
- 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…
- vertex_cover_three_extracts_star_pairsIf the crossing graph of a finite segment family has vertex cover number exactly 3, then one can extract three pairwise-distinct "cover"…
- crossing_points_distinct_of_triangle_freeIf the crossing graph of L is triangle-free and A, B, C are interior intersection points of three star crossing pairs {gᵢ,hᵢ} (with the gᵢ…
- three_crossing_points_of_vertex_cover_threeIf a finite segment family has a triangle-free crossing graph and vertex cover number exactly 3, then there are three pairwise distinct…
- blocking_card_three_of_three_crossing_pointsIf 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…
- 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…
The proof, explained
The proof splits on the vertex cover number of the segment crossing graph. If it is at most 2, the result follows immediately from the base lemma for vertex cover number at most 2. Otherwise, the vertex cover number must be exactly 3, which guarantees the existence of three distinct crossing points between segments in L; from these, a blocked point set of size 3 is constructed, satisfying the required inequality 3 ≤ |P|.
If the crossing graph has vertex cover number at most 2, the desired blocked set exists.
We split into cases based on whether the vertex cover number is at most 2. In this case, the result follows immediately from the previously established lemma triangle_free_blocking_ge_vertex_cover_of_le_two.
uses
triangle_free_blocking_ge_vertex_cover_of_le_twoby_cases h_le2 : (segment_crossing_graph L).vertexCoverNum ≤ 2 · exact triangle_free_blocking_ge_vertex_cover_of_le_two L h_tf h_le2
If the vertex cover number is greater than 2, it must equal 3.
Because the vertex cover number is at most 3, it cannot be ⊤. Converting it from ℕ∞ to ℕ using ENat.natCast_toNat, linear integer arithmetic (omega) deduces from ≤ 3 and ¬(≤ 2) that the vertex cover number is exactly 3.
uses
ENat.natCast_toNat· have h_eq3 : (segment_crossing_graph L).vertexCoverNum = 3 := by have htop : (segment_crossing_graph L).vertexCoverNum ≠ ⊤ := by intro htop_eq rw [htop_eq] at h_vc revert h_vc decide rw [← ENat.natCast_toNat htop] at h_vc h_le2 ⊢ norm_cast at h_vc h_le2 ⊢ omega
There exist three distinct crossing points formed by pairs of segments in L.
By three_crossing_points_of_vertex_cover_three, since the crossing graph is triangle-free and has vertex cover number 3, there are three pairs of segments in L intersecting at three distinct points A, B, and C.
uses
three_crossing_points_of_vertex_cover_threeobtain ⟨a₁, a₂, b₁, b₂, c₁, c₂, d₁, d₂, e₁, e₂, f₁, f₂, A, B, C, ha, hb, hc, hd, he, hf, hab, hcd, hef, hA₁, hA₂, hB₁, hB₂, hC₁, hC₂, hAB, hBC, hCA⟩ := three_crossing_points_of_vertex_cover_three L h_tf h_eq3There exists a 3-element point set blocked by L.
Applying blocking_card_three_of_three_crossing_points to L and the three distinct crossing points produces a point set P of cardinality 3 that is blocked by L.
uses
blocking_card_three_of_three_crossing_pointsobtain ⟨P, hP_block, hP_card⟩ := blocking_card_three_of_three_crossing_points L h_tf a₁ a₂ b₁ b₂ c₁ c₂ d₁ d₂ e₁ e₂ f₁ f₂ A B C ha hb hc hd he hf hab hcd hef hA₁ hA₂ hB₁ hB₂ hC₁ hC₂ hAB hBC hCAThe set P satisfies the required conditions.
We witness the existential with P. The blocking condition holds by construction, and substituting the vertex cover number (3) and the cardinality of P (3) leaves 3 ≤ 3, which is verified by computation.
refine ⟨P, hP_block, ?_⟩ rw [h_eq3, hP_card] decide
triangle_free_blocking_ge_vertex_cover_of_le_two- For any finite family of segments L whose crossing graph is triangle-free and has vertex cover number at most 2, there exists a blocked point set P with cardinality at least the vertex cover number.
ENat.natCast_toNat- An extended natural number n that is not infinity (⊤) equals the cast of its natural number conversion n.toNat.
three_crossing_points_of_vertex_cover_three- If the crossing graph of a finite segment family L is triangle-free and has vertex cover number 3, there exist three pairs of intersecting segments from L intersecting at three pairwise distinct points.
blocking_card_three_of_three_crossing_points- Given three pairwise distinct crossing points of segments in a finite family L whose crossing graph is triangle-free, there exists a 3-element point set blocked by L.
- The vertex cover number is valued in the extended natural numbers (ℕ∞), so concluding that a value at most 3 and strictly greater than 2 equals 3 requires explicitly showing it is finite (not ⊤) before casting to ℕ and applying integer arithmetic.
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.
/-- For every finite family of line segments L whose crossing graph is triangle-free and has vertex cover number at most 3, there exists a point set P blocked by L with cardinality at least the vertex cover number. -/theorem triangle_free_blocking_ge_vertex_cover_of_le_three (L : Finset (Sym2 (ℝ × ℝ))) (h_tf : (segment_crossing_graph L).CliqueFree 3) (h_vc : (segment_crossing_graph L).vertexCoverNum ≤ 3) : ∃ P : Finset (ℝ × ℝ), segments_block_points L P ∧ (segment_crossing_graph L).vertexCoverNum ≤ P.card := by by_cases h_le2 : (segment_crossing_graph L).vertexCoverNum ≤ 2 · exact triangle_free_blocking_ge_vertex_cover_of_le_two L h_tf h_le2 · have h_eq3 : (segment_crossing_graph L).vertexCoverNum = 3 := by have htop : (segment_crossing_graph L).vertexCoverNum ≠ ⊤ := by intro htop_eq rw [htop_eq] at h_vc revert h_vc decide rw [← ENat.natCast_toNat htop] at h_vc h_le2 ⊢ norm_cast at h_vc h_le2 ⊢ omega obtain ⟨a₁, a₂, b₁, b₂, c₁, c₂, d₁, d₂, e₁, e₂, f₁, f₂, A, B, C, ha, hb, hc, hd, he, hf, hab, hcd, hef, hA₁, hA₂, hB₁, hB₂, hC₁, hC₂, hAB, hBC, hCA⟩ := three_crossing_points_of_vertex_cover_three L h_tf h_eq3 obtain ⟨P, hP_block, hP_card⟩ := blocking_card_three_of_three_crossing_points L h_tf a₁ a₂ b₁ b₂ c₁ c₂ d₁ d₂ e₁ e₂ f₁ f₂ A B C ha hb hc hd he hf hab hcd hef hA₁ hA₂ hB₁ hB₂ hC₁ hC₂ hAB hBC hCA refine ⟨P, hP_block, ?_⟩ rw [h_eq3, hP_card] decide