AFTD Auto-Formalizing Theoretical Domains

IsDirectedWalk

inductive

An inductive predicate IsDirectedWalk G u w p stating that a list of edges p : List E forms a directed walk from vertex u to vertex w in the directed multigraph G.

Statement

inductive IsDirectedWalk {V E : Type*} (G : DirectedMultigraph V E) : V → V → List E → Prop
Defined in
arXiv:2611.12330 Section 2
Verified
13 Nov 2026
Axioms
none listed
Built on 1
  • DirectedMultigraphA directed multigraph parameterized by vertex type V and edge type E, with source and target maps src : E → V and tgt : E → V.
Used by 1
  • directedDistENNThe shortest path distance directedDistENN G ℓ u v from vertex u to vertex v in a directed multigraph G with edge lengths ℓ : E → ENNReal,…

Read back from the Lean

IsDirectedWalk G u w p is an inductive predicate asserting that a list of edges p : List E forms a valid directed walk from vertex u : V to vertex w : V in the directed multigraph G : DirectedMultigraph V E. It is defined inductively by two constructors: 1. nil: For every vertex v : V, the empty list [] is a directed walk from v to v in G. 2. cons: For all vertices u, v, w : V, an edge e : E, and an edge list p : List E, if the source of e is u (G.src e = u), the target of e is v (G.tgt e = v), and p is a directed walk from v to w in G, then the prepended list e :: p is a directed walk from u to w in G.

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

/-- Inductive predicate for a directed walk in a directed multigraph. -/
inductive IsDirectedWalk {V E : Type*} (G : DirectedMultigraph V E) : V → V → List E → Prop | nil (v : V) : IsDirectedWalk G v v []
  | cons {u v w : V} (e : E) (p : List E)
      (he_src : G.src e = u) (he_tgt : G.tgt e = v)
      (hp : IsDirectedWalk G v w p) : IsDirectedWalk G u w (e :: p)
See it in the graphDiscuss this resultChallenge it