is_geodesic_transversal
def
A 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.
Statement
def is_geodesic_transversal {V : Type*} (G : SimpleGraph V) (S : Finset V) : Prop
- Defined in
- scout/2610-36821-the-edge-geodesic-transversal-problem.md:85
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 1
- 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 3
- 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…
- exists_geodesic_transversal_of_edge_geodesic_transversalFor any finite edge geodesic transversal T in a simple graph G, there exists a finite vertex geodesic transversal S of G such that the…
- geodesic_transversal_numberThe geodesic transversal number gt(G) of a simple graph G is the infimum in ℕ of the set of natural numbers k such that there exists a…
Read back from the Lean
Given a simple graph G on vertex type V and a finite set of vertices S : Finset V, is_geodesic_transversal G S asserts that:
For all pairs of vertices u, v : V and every walk p from u to v in G:
if p is a maximal geodesic in G (meaning: p is a path, its length equals G.dist u v, every neighbor w of u satisfies G.dist w v ≤ p.length, and every neighbor w of v satisfies G.dist u w ≤ p.length),
then there exists some vertex x ∈ S such that x lies on p (i.e., x ∈ p.support).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A finite set S of vertices of G is a geodesic transversal if every maximal geodesic in G contains at least one vertex of S. -/ def is_geodesic_transversal {V : Type*} (G : SimpleGraph V) (S : Finset V) : Prop := ∀ ⦃u v : V⦄ (p : G.Walk u v), is_maximal_geodesic p → ∃ x ∈ S, x ∈ p.support