AFTD Auto-Formalizing Theoretical Domains

is_maximal_geodesic

def

A geodesic p from u to v is maximal if no adjacent vertex at either endpoint extends it to a strictly longer geodesic.

Statement

def is_maximal_geodesic {V : Type*} {G : SimpleGraph V} {u v : V} (p : G.Walk u v) : Prop
Defined in
arXiv:2610.36821 Section 1
Verified
28 Oct 2026
Axioms
none listed
Used by 10

Read back from the Lean

For a type V, a simple graph G on V, vertices u, v : V, and a walk p from u to v in G, is_maximal_geodesic p is defined as the proposition that: 1. p is a path (p.IsPath) and the length of p equals the graph distance G.dist u v, and 2. for every vertex w : V, if w is adjacent to u in G (G.Adj w u), then the graph distance from w to v is at most p.length (G.dist w v ≤ p.length), and 3. for every vertex w : V, if v is adjacent to w in G (G.Adj v w), then the graph distance from u to w is at most p.length (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

/-- A walk is a maximal geodesic if it is a geodesic that cannot be extended at either endpoint. -/
def is_maximal_geodesic {V : Type*} {G : SimpleGraph V} {u v : V} (p : G.Walk u v) : Prop := (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)
See it in the graphDiscuss this resultChallenge it