IsDirectedWalk
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)