AFTD Auto-Formalizing Theoretical Domains

exists_geodesic_transversal_of_edge_geodesic_transversal

theoremverified

For any finite edge geodesic transversal T in a simple graph G, there exists a finite vertex geodesic transversal S of G such that the cardinality of S is at most the cardinality of T.

Statement

theorem exists_geodesic_transversal_of_edge_geodesic_transversal {V : Type*} (G : SimpleGraph V) (T : Finset (Sym2 V)) (hT : is_edge_geodesic_transversal G T) : ∃ S : Finset V, is_geodesic_transversal G S ∧ S.card ≤ T.card
Source
scout/2610-36821-the-edge-geodesic-transversal-problem.md:107
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_geodesic_transversalA finite set S of vertices in a simple graph G is a geodesic transversal if every maximal geodesic in G contains at least one vertex of S.
  • is_edge_geodesic_transversalA finite set S of edges of G is an edge geodesic transversal if every maximal geodesic in G contains at least one edge of S.
  • is_maximal_geodesicA geodesic p from u to v is maximal if no adjacent vertex at either endpoint extends it to a strictly longer geodesic.
Used by 1

Read back from the Lean

For any type V, simple graph G on V, and finite set of edges T (subsets of Sym2 V), if T is an edge geodesic transversal of G, then there exists a finite set of vertices S of V such that S is a geodesic transversal of G and the cardinality of S is less than or equal to the cardinality of T.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To construct a vertex geodesic transversal S from an edge geodesic transversal T, we select one endpoint for each edge of T using classical choice and let S be the image of T under this selection. The cardinality bound |S| ≤ |T| holds immediately for the image of a finite set. Any maximal geodesic path contains an edge of T, and the chosen endpoint of that edge lies in S and on the path, showing S intersects every maximal geodesic.

  1. There is a function `pt : Sym2 V → V` assigning to every edge one of its incident vertices.

    Every unordered pair in `Sym2 V` has the form `s(x, y)` by `Sym2.ind` and therefore contains at least one vertex (namely `x`). Using the axiom of choice via `Classical.choose` and `Classical.choose_spec`, we obtain an endpoint selector `pt` satisfying `pt e ∈ e` for every edge `e`.

    lines 3–9

    uses Sym2.ind, Classical.choose, Classical.choose_spec

      classical
      have sym2_nonempty : ∀ e : Sym2 V, ∃ x : V, x ∈ e := by
        intro e
        induction e using Sym2.ind with
        | _ x y => exact ⟨x, by simp⟩
      let pt : Sym2 V → V := fun e => Classical.choose (sym2_nonempty e)
      have pt_mem : ∀ e : Sym2 V, pt e ∈ e := fun e => Classical.choose_spec (sym2_nonempty e)
  2. The candidate vertex set S = pt(T) satisfies |S| ≤ |T|, and it suffices to prove that S is a geodesic transversal.

    We define S as the image of the finite edge transversal T under `pt`. The image of a finite set has cardinality at most that of the domain set (`Finset.card_image_le`), which yields |S| ≤ |T| and leaves the goal of showing that S intersects every maximal geodesic.

    lines 10–11

    uses Finset.card_image_le

      let S := Finset.image pt T
      refine ⟨S, ?_, Finset.card_image_le⟩
  3. Any maximal geodesic walk p between vertices u and v contains an edge e ∈ T.

    Let p be a maximal geodesic walk. Unfolding the definition of `is_maximal_geodesic` at p yields the exact four conditions required by the edge geodesic transversal hypothesis `hT.2` (p is a path, its length equals dist(u, v), and it cannot be extended at either end without increasing distance). Applying `hT.2` to p provides an edge e ∈ T traversed by p.

    lines 12–18

      intro u v p hp
      have hp' : p.IsPath ∧ p.length = G.dist u v ∧
          (∀ w, G.Adj w u → G.dist w v ≤ p.length) ∧
          (∀ w, G.Adj v w → G.dist u w ≤ p.length) := by
        unfold is_maximal_geodesic at hp
        tauto
      rcases hT.2 p hp' with ⟨e, heT, he_edges⟩
  4. The chosen vertex pt(e) belongs to S and lies on p, completing the proof that S is a geodesic transversal.

    Because e ∈ T, its selected endpoint pt(e) belongs to S = pt(T) by `Finset.mem_image_of_mem`. By `SimpleGraph.Walk.mem_support_iff_exists_mem_edges`, an endpoint of an edge traversed by a walk belongs to the walk's vertex support. Since e is an edge of p and pt(e) ∈ e, pt(e) is in the support of p, so S intersects p.

    lines 19–21

    uses Finset.mem_image_of_mem, SimpleGraph.Walk.mem_support_iff_exists_mem_edges, Or.inr

      refine ⟨pt e, Finset.mem_image_of_mem pt heT, ?_⟩
      rw [SimpleGraph.Walk.mem_support_iff_exists_mem_edges]
      exact Or.inr ⟨e, he_edges, pt_mem e⟩
Sym2.ind
Induction on unordered pairs: to prove a property holds for all pairs in Sym2 α, it suffices to prove it for pairs of the form s(x, y).
Classical.choose
Given a proof that an element satisfying a predicate exists, returns such an element.
Classical.choose_spec
The witness produced by `Classical.choose` satisfies the defining predicate.
Finset.card_image_le
The cardinality of the image of a finite set under a function is at most the cardinality of the original set.
Finset.mem_image_of_mem
If an element a is in a finite set s, then f(a) is in the image of s under f.
SimpleGraph.Walk.mem_support_iff_exists_mem_edges
A vertex belongs to the support (vertex set) of a walk if and only if it is the target vertex or an endpoint of some edge traversed by the walk.
Or.inr
Proves a disjunction a ∨ b from a proof of the right disjunct b.

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

/-- From any finite edge geodesic transversal T, selecting one endpoint per edge yields a finite vertex geodesic transversal S with |S| ≤ |T|. -/theorem exists_geodesic_transversal_of_edge_geodesic_transversal {V : Type*} (G : SimpleGraph V) (T : Finset (Sym2 V)) (hT : is_edge_geodesic_transversal G T) : ∃ S : Finset V, is_geodesic_transversal G S ∧ S.card ≤ T.card := by  classical  have sym2_nonempty : ∀ e : Sym2 V, ∃ x : V, x ∈ e := by    intro e    induction e using Sym2.ind with    | _ x y => exact ⟨x, by simp⟩  let pt : Sym2 V → V := fun e => Classical.choose (sym2_nonempty e)  have pt_mem : ∀ e : Sym2 V, pt e ∈ e := fun e => Classical.choose_spec (sym2_nonempty e)  let S := Finset.image pt T  refine ⟨S, ?_, Finset.card_image_le⟩  intro u v p hp  have hp' : p.IsPath ∧ p.length = G.dist u v ∧      (∀ w, G.Adj w u → G.dist w v ≤ p.length) ∧      (∀ w, G.Adj v w → G.dist u w ≤ p.length) := by    unfold is_maximal_geodesic at hp    tauto  rcases hT.2 p hp' with ⟨e, heT, he_edges⟩  refine ⟨pt e, Finset.mem_image_of_mem pt heT, ?_⟩  rw [SimpleGraph.Walk.mem_support_iff_exists_mem_edges]  exact Or.inr ⟨e, he_edges, pt_mem e⟩
See it in the graphDiscuss this resultChallenge it