vertex_cover_three_extracts_star_pairs
theoremverified
If the crossing graph of a finite segment family has vertex cover number exactly 3, then one can extract three pairwise-distinct "cover" segments g₁,g₂,g₃ together with outside segments h₁,h₂,h₃, such that each hᵢ lies outside {g₁,g₂,g₃} and gᵢ crosses hᵢ — i.e. three crossing pairs attached to three distinct minimum-vertex-cover segments.
Statement
theorem vertex_cover_three_extracts_star_pairs
(L : Finset (Sym2 (ℝ × ℝ)))
(h_vc : (segment_crossing_graph L).vertexCoverNum = 3) :
∃ (g1a g1b g2a g2b g3a g3b h1a h1b h2a h2b h3a h3b : ℝ × ℝ),
s(g1a, g1b) ∈ L ∧ s(g2a, g2b) ∈ L ∧ s(g3a, g3b) ∈ L ∧
s(h1a, h1b) ∈ L ∧ s(h2a, h2b) ∈ L ∧ s(h3a, h3b) ∈ L ∧
s(g1a, g1b) ≠ s(g2a, g2b) ∧ s(g2a, g2b) ≠ s(g3a, g3b) ∧
s(g1a, g1b) ≠ s(g3a, g3b) ∧
s(h1a, h1b) ∉ ({s(g1a, g1b), s(g2a, g2b), s(g3a, g3b)} : Finset (Sym2 (ℝ × ℝ))) ∧
s(h2a, h2b) ∉ ({s(g1a, g1b), s(g2a, g2b), s(g3a, g3b)} : Finset (Sym2 (ℝ × ℝ))) ∧
s(h3a, h3b) ∉ ({s(g1a, g1b), s(g2a, g2b), s(g3a, g3b)} : Finset (Sym2 (ℝ × ℝ))) ∧
segment_crossing s(g1a, g1b) s(h1a, h1b) ∧
segment_crossing s(g2a, g2b) s(h2a, h2b) ∧
segment_crossing s(g3a, g3b) s(h3a, h3b)- Source
- step towards triangle_free_blocking_ge_vertex_cover_of_le_three
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- segment_crossingTwo line segments in the plane, represented as unordered pairs of endpoints in Sym2 (ℝ × ℝ), cross if the intersection of their relative…
- segment_crossing_symmThe segment crossing relation between two segments in ℝ² is symmetric.
- 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 2
- 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…
- 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…
Lean source view module on GitHub
/-- A minimum vertex cover of size 3 yields three star crossing pairs (gᵢ, hᵢ) with the gᵢ distinct and each hᵢ outside the cover. -/ theorem vertex_cover_three_extracts_star_pairs (L : Finset (Sym2 (ℝ × ℝ))) (h_vc : (segment_crossing_graph L).vertexCoverNum = 3) : ∃ (g1a g1b g2a g2b g3a g3b h1a h1b h2a h2b h3a h3b : ℝ × ℝ), s(g1a, g1b) ∈ L ∧ s(g2a, g2b) ∈ L ∧ s(g3a, g3b) ∈ L ∧ s(h1a, h1b) ∈ L ∧ s(h2a, h2b) ∈ L ∧ s(h3a, h3b) ∈ L ∧ s(g1a, g1b) ≠ s(g2a, g2b) ∧ s(g2a, g2b) ≠ s(g3a, g3b) ∧ s(g1a, g1b) ≠ s(g3a, g3b) ∧ s(h1a, h1b) ∉ ({s(g1a, g1b), s(g2a, g2b), s(g3a, g3b)} : Finset (Sym2 (ℝ × ℝ))) ∧ s(h2a, h2b) ∉ ({s(g1a, g1b), s(g2a, g2b), s(g3a, g3b)} : Finset (Sym2 (ℝ × ℝ))) ∧ s(h3a, h3b) ∉ ({s(g1a, g1b), s(g2a, g2b), s(g3a, g3b)} : Finset (Sym2 (ℝ × ℝ))) ∧ segment_crossing s(g1a, g1b) s(h1a, h1b) ∧ segment_crossing s(g2a, g2b) s(h2a, h2b) ∧ segment_crossing s(g3a, g3b) s(h3a, h3b) := by classical set G := segment_crossing_graph L with hGdef have hvc : G.vertexCoverNum = 3 := by rw [hGdef]; exact h_vc obtain ⟨C, hCcard, hCcov⟩ := SimpleGraph.vertexCoverNum_exists G rw [hvc] at hCcard have hCfin : C.Finite := by rw [← Set.encard_lt_top_iff, hCcard] exact ENat.natCast_lt_top 3 have key : ∀ g ∈ C, ∃ h : ↥L, G.Adj g h ∧ h ∉ C := by intro g hg by_contra hcon push Not at hcon have hcov' : G.IsVertexCover (C \ {g}) := by intro u v huv rcases hCcov huv with hu | hv · by_cases hug : u = g · subst hug exact Or.inr ⟨hcon v huv, by simp [huv.ne']⟩ · exact Or.inl ⟨hu, by simp [hug]⟩ · by_cases hvg : v = g · subst hvg exact Or.inl ⟨hcon u huv.symm, by simp [huv.ne]⟩ · exact Or.inr ⟨hv, by simp [hvg]⟩ have hle := SimpleGraph.IsVertexCover.vertexCoverNum_le hcov' rw [hvc] at hle have h2 : (C \ {g}).encard = 2 := by rw [Set.encard_sdiff_singleton_of_mem hg, hCcard] decide rw [h2] at hle exact absurd hle (by decide) have hCts_card : hCfin.toFinset.card = 3 := by have h := Set.Finite.encard_eq_coe_toFinset_card hCfin rw [hCcard] at h exact_mod_cast h.symm obtain ⟨g1, g2, g3, h12, h13, h23, hCts_eq⟩ := Finset.card_eq_three.mp hCts_card have hg1C : g1 ∈ C := by rw [← Set.Finite.mem_toFinset hCfin, hCts_eq]; simp have hg2C : g2 ∈ C := by rw [← Set.Finite.mem_toFinset hCfin, hCts_eq]; simp have hg3C : g3 ∈ C := by rw [← Set.Finite.mem_toFinset hCfin, hCts_eq]; simp obtain ⟨h1, hh1adj, hh1C⟩ := key g1 hg1C obtain ⟨h2, hh2adj, hh2C⟩ := key g2 hg2C obtain ⟨h3, hh3adj, hh3C⟩ := key g3 hg3C have split : ∀ e : Sym2 (ℝ × ℝ), ∃ a b : ℝ × ℝ, e = s(a, b) := by intro e exact Sym2.ind (fun a b => ⟨a, b, rfl⟩) e obtain ⟨g1a, g1b, hg1e⟩ := split g1.val obtain ⟨g2a, g2b, hg2e⟩ := split g2.val obtain ⟨g3a, g3b, hg3e⟩ := split g3.val obtain ⟨h1a, h1b, hh1e⟩ := split h1.val obtain ⟨h2a, h2b, hh2e⟩ := split h2.val obtain ⟨h3a, h3b, hh3e⟩ := split h3.val have adj_cross : ∀ u v : ↥L, G.Adj u v → segment_crossing u.val v.val := by intro u v huv rw [hGdef] at huv simp only [segment_crossing_graph, SimpleGraph.fromRel] at huv rcases huv.2 with hc | hc · exact hc · exact (segment_crossing_symm _ _).mp hc have outside : ∀ h : ↥L, h ∉ C → h.val ∉ ({g1.val, g2.val, g3.val} : Finset (Sym2 (ℝ × ℝ))) := by intro h hh have hh' : h ∉ hCfin.toFinset := by rw [Set.Finite.mem_toFinset]; exact hh rw [hCts_eq] at hh' simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hh' simp only [Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨fun h1' => hh'.1 (Subtype.ext h1'), fun h2' => hh'.2.1 (Subtype.ext h2'), fun h3' => hh'.2.2 (Subtype.ext h3')⟩ refine ⟨g1a, g1b, g2a, g2b, g3a, g3b, h1a, h1b, h2a, h2b, h3a, h3b, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · rw [← hg1e]; exact g1.2 · rw [← hg2e]; exact g2.2 · rw [← hg3e]; exact g3.2 · rw [← hh1e]; exact h1.2 · rw [← hh2e]; exact h2.2 · rw [← hh3e]; exact h3.2 · rw [← hg1e, ← hg2e]; exact fun hh => h12 (Subtype.ext hh) · rw [← hg2e, ← hg3e]; exact fun hh => h23 (Subtype.ext hh) · rw [← hg1e, ← hg3e]; exact fun hh => h13 (Subtype.ext hh) · rw [← hh1e, ← hg1e, ← hg2e, ← hg3e]; exact outside h1 hh1C · rw [← hh2e, ← hg1e, ← hg2e, ← hg3e]; exact outside h2 hh2C · rw [← hh3e, ← hg1e, ← hg2e, ← hg3e]; exact outside h3 hh3C · rw [← hg1e, ← hh1e]; exact adj_cross g1 h1 hh1adj · rw [← hg2e, ← hh2e]; exact adj_cross g2 h2 hh2adj · rw [← hg3e, ← hh3e]; exact adj_cross g3 h3 hh3adj