digraph_reach_within
def
digraph_reach_within D k u v: there is a directed walk of length at most k from u to v in the digraph D (equivalently, the directed distance from u to v is at most k). For k = 0 it means u = v; for k + 1 either a walk of length at most k exists or u has an out-neighbour w with a walk of length at most k from w to v.
Statement
def digraph_reach_within {V : Type*} (D : Digraph V) : ℕ → V → V → Prop
- Defined in
- arXiv:2610.09648 (An asymptotically tight bound on oriented diameter), Section 1: the directed distance dist(x,y) of an orientation (length of a shortest directed x-y path); this predicate says dist(x,y) <= k.
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 7
- cycle_graph_eight_strong_orientation_diameter_le_sevenSanity (non-vacuity): the 8-cycle, a bridgeless graph of diameter 4, has a strong orientation of directed diameter at most 7, namely the…
- oriented_diameter_bound_holds_monoIf every connected bridgeless graph of diameter d has a strong orientation of diameter at most k, the same holds for every k' >= k (f(d)…
- digraph_reach_within_monoReachability within k steps implies reachability within any k' >= k steps.
- oriented_diameter_four_lower_boundf(4) >= 12: there is a finite connected bridgeless simple graph of diameter 4 that has no strong orientation of directed diameter at most…
- has_strong_orientation_of_diameter_leThe simple graph G has an orientation D (each edge of G gets exactly one direction, no other arcs) in which every ordered pair of vertices…
- digraph_reach_within_one_of_adjSanity: an arc u -> v is a directed walk of length at most 1 from u to v.
- digraph_reach_within_zero_iffSanity: a directed walk of length at most 0 from u to v exists iff u = v.
Lean source view module on GitHub
def digraph_reach_within {V : Type*} (D : Digraph V) : ℕ → V → V → Prop | 0, u, v => u = v | k + 1, u, v => digraph_reach_within D k u v ∨ ∃ w, D.Adj u w ∧ digraph_reach_within D k w v