AFTD Auto-Formalizing Theoretical Domains

triangle_free_blocking_ge_vertex_cover_of_le_three

theoremverified

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

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|.

  1. 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.

    lines 8–9

    uses triangle_free_blocking_ge_vertex_cover_of_le_two

      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
  2. 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.

    lines 10–18

    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
  3. 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.

    lines 19–22

    uses three_crossing_points_of_vertex_cover_three

        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
  4. There 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.

    lines 23–27

    uses blocking_card_three_of_three_crossing_points

        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
  5. The 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.

    lines 28–30

        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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it