AFTD Auto-Formalizing Theoretical Domains

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

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