AFTD Auto-Formalizing Theoretical Domains

triangle_free_blocking_ge_vertex_cover_of_le_one

theoremverified

For every finite family of line segments L whose crossing graph has vertex cover number at most 1, 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_one
    (L : Finset (Sym2 (ℝ × ℝ)))
    (h_vc : (segment_crossing_graph L).vertexCoverNum ≤ 1) :
    ∃ P : Finset (ℝ × ℝ), segments_block_points L P ∧
      (segment_crossing_graph L).vertexCoverNum ≤ P.card
Source
step towards triangle_free_blocking_ge_vertex_cover
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • segments_block_points_of_card_le_oneAny finite point set in ℝ² of cardinality at most 1 is vacuously blocked by any finite family of segments L under the triangle-free…
  • 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…
Used by 1

Lean source view module on GitHub

/-- The triangle-free blocking lower bound holds when the crossing graph has vertex cover number at most 1. -/
theorem triangle_free_blocking_ge_vertex_cover_of_le_one
    (L : Finset (Sym2 (ℝ × ℝ)))
    (h_vc : (segment_crossing_graph L).vertexCoverNum ≤ 1) :
    ∃ P : Finset (ℝ × ℝ), segments_block_points L P ∧
      (segment_crossing_graph L).vertexCoverNum ≤ P.card := by
  refine ⟨{(0, 0)}, segments_block_points_of_card_le_one L (by simp), by simp [h_vc]⟩
See it in the graphDiscuss this resultChallenge it