exists_geodesic_transversal_of_edge_geodesic_transversal
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
- geodesic_transversal_number_le_edge_geodesic_transversal_numberFor any connected simple graph G that admits a finite edge geodesic transversal, the vertex geodesic transversal number of G is bounded…
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.
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`.
uses
Sym2.ind,Classical.choose,Classical.choose_specclassical 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)
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.
uses
Finset.card_image_lelet S := Finset.image pt T refine ⟨S, ?_, Finset.card_image_le⟩
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.
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⟩
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.
uses
Finset.mem_image_of_mem,SimpleGraph.Walk.mem_support_iff_exists_mem_edges,Or.inrrefine ⟨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.
- The proof relies on classical choice (`Classical.choose`) to select an endpoint for each edge represented as an element of the symmetric square `Sym2 V`.
- The definition of `is_edge_geodesic_transversal` inlines the four conjuncts of a maximal geodesic path, whereas `is_geodesic_transversal` uses the definition `is_maximal_geodesic`; lines 13–17 bridge this purely syntactic difference via `unfold` and `tauto`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩