geodesic_transversal_number
The 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 finite geodesic transversal S of G with cardinality k.
Statement
noncomputable def geodesic_transversal_number {V : Type*} (G : SimpleGraph V) : ℕ
- Defined in
- scout/2610-36821-the-edge-geodesic-transversal-problem.md:85
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 1
- 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.
- 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 a simple graph G on vertex type V, geodesic_transversal_number G is defined as the infimum (in ℕ, which is the minimum, or 0 if empty) of the set of all natural numbers k such that there exists a finite subset S : Finset V with cardinality k that is a geodesic transversal of G.
A finite set S is a geodesic transversal of G if for all vertices u, v : V and every walk p from u to v, if p is a maximal geodesic, then S contains at least one vertex in the support of p.
A walk p from u to v is a maximal geodesic if:
1. p is a path and its length equals the graph distance G.dist u v,
2. for all vertices w adjacent to u, G.dist w v ≤ p.length, and
3. for all vertices w adjacent to v, G.dist u w ≤ p.length.
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
/-- The geodesic transversal number of a simple graph G is the infimum in ℕ of the cardinalities of all finite geodesic transversals of G. -/ noncomputable def geodesic_transversal_number {V : Type*} (G : SimpleGraph V) : ℕ := sInf { k : ℕ | ∃ S : Finset V, is_geodesic_transversal G S ∧ S.card = k }