AFTD Auto-Formalizing Theoretical Domains

not_cliqueFree_three_of_crosses_crossing_pair_tf

theoremverified

If 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 inserting uv creates a triangle in the crossing graph.

Statement

theorem not_cliqueFree_three_of_crosses_crossing_pair_tf
    (L : Finset (Sym2 (ℝ × ℝ)))
    (_h_tf : (segment_crossing_graph L).CliqueFree 3)
    (s₁ s₂ : Sym2 (ℝ × ℝ))
    (hs₁ : s₁ ∈ L) (hs₂ : s₂ ∈ L) (hs₁₂ : s₁ ≠ s₂)
    (hcross₁₂ : segment_crossing s₁ s₂)
    (u v : ℝ × ℝ)
    (h_ne1 : s(u, v) ≠ s₁) (h_ne2 : s(u, v) ≠ s₂)
    (hcross_u1 : segment_crossing s(u, v) s₁)
    (hcross_u2 : segment_crossing s(u, v) s₂) :
    ¬ (segment_crossing_graph (insert s(u, v) L)).CliqueFree 3
Source
step towards triangle_free_blocking_ge_vertex_cover
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • segment_crossingTwo line segments in the plane, represented as unordered pairs of endpoints in Sym2 (ℝ × ℝ), cross if the intersection of their relative…
  • 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

The proof, explained

To prove that inserting the segment uv into the segment family L creates a triangle in the crossing graph, the proof explicitly constructs a 3-clique. It defines the three vertices corresponding to uv, s₁, and s₂ in the augmented collection L' = insert(uv, L) and verifies that they are pairwise distinct. Since s₁ crosses s₂ and uv crosses both s₁ and s₂, all three pairs are adjacent, forming a 3-clique and thereby showing the crossing graph of L' is not 3-clique-free.

  1. Introduce the augmented segment set L' = L ∪ {uv} and represent uv, s₁, and s₂ as vertices x₀, x₁, x₂ of L'.

    We define L' as the finset obtained by inserting the new segment s(u, v) into L. We then instantiate three vertices in the subtype of elements of L': x₀ corresponding to s(u, v) (which is in L' by definition), and x₁ and x₂ corresponding to s₁ and s₂ respectively (which belong to L' because they already belong to L).

    lines 13–17

      classical
      let L' : Finset (Sym2 (ℝ × ℝ)) := insert s(u, v) L
      let x0 : L' := ⟨s(u, v), by simp [L']⟩
      let x1 : L' := ⟨s₁, by simp [L', hs₁]⟩
      let x2 : L' := ⟨s₂, by simp [L', hs₂]⟩
  2. The vertices x₀, x₁, and x₂ are pairwise distinct.

    For each pair, equality of the subtype vertices would imply equality of the underlying segments via `Subtype.ext_iff.mp`. This immediately contradicts the assumptions that s(u, v) ≠ s₁, s(u, v) ≠ s₂, and s₁ ≠ s₂, establishing x₀ ≠ x₁, x₀ ≠ x₂, and x₁ ≠ x₂.

    lines 18–26

    uses Subtype.ext_iff.mp

      have h01 : x0 ≠ x1 := by
        intro h
        exact h_ne1 (Subtype.ext_iff.mp h)
      have h02 : x0 ≠ x2 := by
        intro h
        exact h_ne2 (Subtype.ext_iff.mp h)
      have h12 : x1 ≠ x2 := by
        intro h
        exact hs₁₂ (Subtype.ext_iff.mp h)
  3. The vertices x₀, x₁, and x₂ are pairwise adjacent in the crossing graph of L'.

    By definition of `segment_crossing_graph` and rewriting with `SimpleGraph.fromRel_adj`, two distinct vertices in L' are adjacent if and only if their underlying segments cross. Since x₀ ≠ x₁ and s(u, v) crosses s₁, x₀ and x₁ are adjacent via `Or.inl`. Likewise, s(u, v) crossing s₂ yields adjacency between x₀ and x₂, and s₁ crossing s₂ yields adjacency between x₁ and x₂.

    lines 27–35

    uses segment_crossing_graph, SimpleGraph.fromRel_adj, Or.inl

      have hadj01 : (segment_crossing_graph L').Adj x0 x1 := by
        rw [segment_crossing_graph, SimpleGraph.fromRel_adj]
        exact ⟨h01, Or.inl hcross_u1⟩
      have hadj02 : (segment_crossing_graph L').Adj x0 x2 := by
        rw [segment_crossing_graph, SimpleGraph.fromRel_adj]
        exact ⟨h02, Or.inl hcross_u2⟩
      have hadj12 : (segment_crossing_graph L').Adj x1 x2 := by
        rw [segment_crossing_graph, SimpleGraph.fromRel_adj]
        exact ⟨h12, Or.inl hcross₁₂⟩
  4. The vertex subset t = {x₀, x₁, x₂} has cardinality 3.

    We define the finset t = {x₀, x₁, x₂}. Because the three vertices have already been proven pairwise distinct, simplifying the cardinality of this 3-element set yields |t| = 3.

    lines 36–38

      let t : Finset L' := {x0, x1, x2}
      have hcard : t.card = 3 := by
        simp [t, h01, h02, h12]
  5. The set t forms a clique in the crossing graph of L'.

    By `SimpleGraph.isClique_iff`, t is a clique if every pair of distinct elements in t is adjacent. Given distinct vertices a, b ∈ t, each must be one of x₀, x₁, or x₂. Case analysis shows that whenever a = b, distinctness gives a contradiction, and whenever a ≠ b, adjacency follows directly from one of the three established pairwise adjacencies or its symmetry.

    lines 39–45

    uses SimpleGraph.isClique_iff

      have hclique : (segment_crossing_graph L').IsClique (↑t : Set L') := by
        rw [SimpleGraph.isClique_iff]
        intro a ha b hb hab
        simp [t] at ha hb
        rcases ha with rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl <;>
          first | exact hadj01 | exact hadj02 | exact hadj12 |
            exact hadj01.symm | exact hadj02.symm | exact hadj12.symm | contradiction
  6. The crossing graph of L' contains a 3-clique and is therefore not triangle-free.

    Combining the clique property of t with the fact that |t| = 3 shows that t is an explicit 3-clique (`IsNClique 3`). The existence of a 3-clique refutes the assertion that the graph is 3-clique-free.

    lines 46–47

      have hnic : (segment_crossing_graph L').IsNClique 3 t := ⟨hclique, hcard⟩
      exact hnic.not_cliqueFree
SimpleGraph.fromRel_adj
In a simple graph generated from a binary relation r, two vertices v and w are adjacent if and only if v ≠ w and either r(v, w) or r(w, v) holds.
SimpleGraph.isClique_iff
A set of vertices s forms a clique in a graph G if and only if every pair of distinct vertices in s is adjacent.
Or.inl
The left constructor of a disjunction: deduces A ∨ B from a proof of A.
Subtype.ext_iff.mp
Equality of two elements in a subtype implies equality of their underlying values.
segment_crossing_graph
The simple graph on a finite set of segments whose edges connect distinct segments that cross.

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

/-- If a segment uv crosses both members of a crossing pair in L, then inserting uv creates a triangle in the crossing graph. -/theorem not_cliqueFree_three_of_crosses_crossing_pair_tf    (L : Finset (Sym2 (ℝ × ℝ)))    (_h_tf : (segment_crossing_graph L).CliqueFree 3)    (s₁ s₂ : Sym2 (ℝ × ℝ))    (hs₁ : s₁ ∈ L) (hs₂ : s₂ ∈ L) (hs₁₂ : s₁ ≠ s₂)    (hcross₁₂ : segment_crossing s₁ s₂)    (u v : ℝ × ℝ)    (h_ne1 : s(u, v) ≠ s₁) (h_ne2 : s(u, v) ≠ s₂)    (hcross_u1 : segment_crossing s(u, v) s₁)    (hcross_u2 : segment_crossing s(u, v) s₂) :    ¬ (segment_crossing_graph (insert s(u, v) L)).CliqueFree 3 := by  classical  let L' : Finset (Sym2 (ℝ × ℝ)) := insert s(u, v) L  let x0 : L' := ⟨s(u, v), by simp [L']⟩  let x1 : L' := ⟨s₁, by simp [L', hs₁]⟩  let x2 : L' := ⟨s₂, by simp [L', hs₂]⟩  have h01 : x0 ≠ x1 := by    intro h    exact h_ne1 (Subtype.ext_iff.mp h)  have h02 : x0 ≠ x2 := by    intro h    exact h_ne2 (Subtype.ext_iff.mp h)  have h12 : x1 ≠ x2 := by    intro h    exact hs₁₂ (Subtype.ext_iff.mp h)  have hadj01 : (segment_crossing_graph L').Adj x0 x1 := by    rw [segment_crossing_graph, SimpleGraph.fromRel_adj]    exact ⟨h01, Or.inl hcross_u1⟩  have hadj02 : (segment_crossing_graph L').Adj x0 x2 := by    rw [segment_crossing_graph, SimpleGraph.fromRel_adj]    exact ⟨h02, Or.inl hcross_u2⟩  have hadj12 : (segment_crossing_graph L').Adj x1 x2 := by    rw [segment_crossing_graph, SimpleGraph.fromRel_adj]    exact ⟨h12, Or.inl hcross₁₂⟩  let t : Finset L' := {x0, x1, x2}  have hcard : t.card = 3 := by    simp [t, h01, h02, h12]  have hclique : (segment_crossing_graph L').IsClique (↑t : Set L') := by    rw [SimpleGraph.isClique_iff]    intro a ha b hb hab    simp [t] at ha hb    rcases ha with rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl <;>      first | exact hadj01 | exact hadj02 | exact hadj12 |        exact hadj01.symm | exact hadj02.symm | exact hadj12.symm | contradiction  have hnic : (segment_crossing_graph L').IsNClique 3 t := ⟨hclique, hcard⟩  exact hnic.not_cliqueFree
See it in the graphDiscuss this resultChallenge it