AFTD Auto-Formalizing Theoretical Domains

is_edge_geodesic_transversal

def

A 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.

Statement

def is_edge_geodesic_transversal {V : Type*} (G : SimpleGraph V) (S : Finset (Sym2 V)) : Prop
Defined in
arXiv:2610.36821 Section 1
Verified
28 Oct 2026
Axioms
none listed
Used by 9

Read back from the Lean

For a type V, a simple graph G on V, and a finite set S of unordered pairs of vertices (Sym2 V), is_edge_geodesic_transversal G S asserts that: 1. Every element e ∈ S is an edge of G (e ∈ G.edgeSet). 2. For all vertices u, v : V and every walk p in G from u to v, if: - p is a path (p.IsPath), - the length of p equals the graph distance between u and v (p.length = G.dist u v), - for every vertex w adjacent to u, G.dist w v ≤ p.length, and - for every vertex w adjacent to v, G.dist u w ≤ p.length, then there exists an edge e ∈ S that appears in p.edges.

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 of edges S in G is an edge geodesic transversal if every maximal geodesic of G contains at least one edge of S. -/
def is_edge_geodesic_transversal {V : Type*} (G : SimpleGraph V) (S : Finset (Sym2 V)) : Prop := (∀ e ∈ S, e ∈ G.edgeSet) ∧
  ∀ ⦃u v : V⦄ (p : G.Walk u v),
    (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)) →
    ∃ e ∈ S, e ∈ p.edges
See it in the graphDiscuss this resultChallenge it