AFTD Auto-Formalizing Theoretical Domains

digraph_dist_le

deforiginal

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
See it in the graphDiscuss this resultChallenge it