three_crossing_points_of_vertex_cover_three
theoremverified
If a finite segment family has a triangle-free crossing graph and vertex cover number exactly 3, then there are three pairwise distinct points, each lying in the relative interiors of the two segments of one of three distinct crossing pairs of the family.
Statement
theorem three_crossing_points_of_vertex_cover_three
(L : Finset (Sym2 (ℝ × ℝ)))
(h_tf : (segment_crossing_graph L).CliqueFree 3)
(h_vc : (segment_crossing_graph L).vertexCoverNum = 3) :
∃ (a₁ a₂ b₁ b₂ c₁ c₂ d₁ d₂ e₁ e₂ f₁ f₂ A B C : ℝ × ℝ),
s(a₁, a₂) ∈ L ∧ s(b₁, b₂) ∈ L ∧ s(c₁, c₂) ∈ L ∧
s(d₁, d₂) ∈ L ∧ s(e₁, e₂) ∈ L ∧ s(f₁, f₂) ∈ L ∧
s(a₁, a₂) ≠ s(b₁, b₂) ∧ s(c₁, c₂) ≠ s(d₁, d₂) ∧ s(e₁, e₂) ≠ s(f₁, f₂) ∧
A ∈ openSegment ℝ a₁ a₂ ∧ A ∈ openSegment ℝ b₁ b₂ ∧
B ∈ openSegment ℝ c₁ c₂ ∧ B ∈ openSegment ℝ d₁ d₂ ∧
C ∈ openSegment ℝ e₁ e₂ ∧ C ∈ openSegment ℝ f₁ f₂ ∧
A ≠ B ∧ B ≠ C ∧ C ≠ A- Source
- step towards triangle_free_blocking_ge_vertex_cover_of_le_three
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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ᵢ…
- 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…
- segment_crossingTwo line segments in the plane, represented as unordered pairs of endpoints in Sym2 (ℝ × ℝ), cross if the intersection of their relative…
- 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…
Lean source view module on GitHub
/-- Vertex cover number 3 plus triangle-freeness yields three distinct crossing points, each interior to two distinct segments of L. -/ theorem three_crossing_points_of_vertex_cover_three (L : Finset (Sym2 (ℝ × ℝ))) (h_tf : (segment_crossing_graph L).CliqueFree 3) (h_vc : (segment_crossing_graph L).vertexCoverNum = 3) : ∃ (a₁ a₂ b₁ b₂ c₁ c₂ d₁ d₂ e₁ e₂ f₁ f₂ A B C : ℝ × ℝ), s(a₁, a₂) ∈ L ∧ s(b₁, b₂) ∈ L ∧ s(c₁, c₂) ∈ L ∧ s(d₁, d₂) ∈ L ∧ s(e₁, e₂) ∈ L ∧ s(f₁, f₂) ∈ L ∧ s(a₁, a₂) ≠ s(b₁, b₂) ∧ s(c₁, c₂) ≠ s(d₁, d₂) ∧ s(e₁, e₂) ≠ s(f₁, f₂) ∧ A ∈ openSegment ℝ a₁ a₂ ∧ A ∈ openSegment ℝ b₁ b₂ ∧ B ∈ openSegment ℝ c₁ c₂ ∧ B ∈ openSegment ℝ d₁ d₂ ∧ C ∈ openSegment ℝ e₁ e₂ ∧ C ∈ openSegment ℝ f₁ f₂ ∧ A ≠ B ∧ B ≠ C ∧ C ≠ A := by obtain ⟨g1a, g1b, g2a, g2b, g3a, g3b, h1a, h1b, h2a, h2b, h3a, h3b, hg1, hg2, hg3, hh1, hh2, hh3, hgg12, hgg23, hgg13, hh1out, hh2out, hh3out, hx1, hx2, hx3⟩ := vertex_cover_three_extracts_star_pairs L h_vc simp only [segment_crossing, Sym2.lift_mk, Set.Nonempty, Set.mem_inter_iff] at hx1 hx2 hx3 obtain ⟨A, hA1, hA2⟩ := hx1 obtain ⟨B, hB1, hB2⟩ := hx2 obtain ⟨C, hC1, hC2⟩ := hx3 have h_dist := crossing_points_distinct_of_triangle_free L h_tf g1a g1b g2a g2b g3a g3b h1a h1b h2a h2b h3a h3b A B C hg1 hg2 hg3 hh1 hh2 hh3 hgg12 hgg23 hgg13 hh1out hh2out hh3out hA1 hA2 hB1 hB2 hC1 hC2 have hne1 : s(g1a, g1b) ≠ s(h1a, h1b) := by intro h; apply hh1out; simp [← h] have hne2 : s(g2a, g2b) ≠ s(h2a, h2b) := by intro h; apply hh2out; simp [← h] have hne3 : s(g3a, g3b) ≠ s(h3a, h3b) := by intro h; apply hh3out; simp [← h] refine ⟨g1a, g1b, h1a, h1b, g2a, g2b, h2a, h2b, g3a, g3b, h3a, h3b, A, B, C, hg1, hh1, hg2, hh2, hg3, hh3, hne1, hne2, hne3, hA1, hA2, hB1, hB2, hC1, hC2, h_dist.1, h_dist.2.1, h_dist.2.2.symm⟩