AFTD Auto-Formalizing Theoretical Domains

geodesic_transversal_number

def

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

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 }
See it in the graphDiscuss this resultChallenge it