digraph_dist_le
A vertex x reaches y in at most β steps in digraph D if there exists a sequence of vertices starting at x and ending at y of length at most β + 1 where each consecutive pair is adjacent in D.
Statement
def digraph_dist_le {W : Type*} (D : Digraph W) (x y : W) (β : ℕ) : Prop
- Related work
- folklore
- Verified
- 06 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a type W, a directed graph D : Digraph W, vertices x, y : W, and a natural number β : ℕ, digraph_dist_le D x y β is defined as the proposition that there exists a list l of vertices in W such that:
1. The head of l is x (l.head? = some x),
2. The last element of l is y (l.getLast? = some y),
3. The number of steps (edges) l.length - 1 is at most β, and
4. l is a chain under the adjacency relation D.Adj (l.IsChain D.Adj, i.e., consecutive elements in l are connected by a directed edge in D).
Equivalently, this asserts the existence of a directed walk in D from x to y of length at most β.
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 vertex x reaches y in at most β steps in digraph D along a directed walk. -/ def digraph_dist_le {W : Type*} (D : Digraph W) (x y : W) (β : ℕ) : Prop := ∃ l : List W, l.head? = some x ∧ l.getLast? = some y ∧ l.length - 1 ≤ β ∧ l.IsChain D.Adj