AFTD Auto-Formalizing Theoretical Domains

digraph_is_directed_path

def

A directed path from u to v in a digraph D is a list of vertices p forming a directed chain in D with no duplicate vertices, starting at u and ending at v.

Statement

def digraph_is_directed_path {V : Type*} (D : Digraph V) (p : List V) (u v : V) : Prop
Defined in
Bang-Jensen and Gutin, Digraphs: Theory, Algorithms and Applications, 2009
Verified
28 Oct 2026
Axioms
none listed
Used by 20

Read back from the Lean

For a vertex type V, a directed graph D : Digraph V, a list of vertices p : List V, and vertices u, v : V, digraph_is_directed_path D p u v defines the proposition that p is a simple (non-self-intersecting) directed path from u to v in D. That is, all of the following hold: 1. p.IsChain D.Adj: for every pair of consecutive elements x then y in the list p, there is a directed edge from x to y (D.Adj x y); 2. p.Nodup: all vertices in p are pairwise distinct (no vertex is visited more than once); 3. p.head? = some u: the first element of p is u (in particular, p is non-empty); 4. p.getLast? = some v: the last element of p is v.

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 directed path in a digraph D is a nodup chain of directed edges from u to v. -/
def digraph_is_directed_path {V : Type*} (D : Digraph V) (p : List V) (u v : V) : Prop := p.IsChain D.Adj ∧ p.Nodup ∧ p.head? = some u ∧ p.getLast? = some v
See it in the graphDiscuss this resultChallenge it