digraph_reach_within_mono
Reachability within k steps implies reachability within any k' >= k steps.
Statement
theorem digraph_reach_within_mono {V : Type*} (D : Digraph V) {k k' : ℕ} (hk : k ≤ k') (u v : V) (h : digraph_reach_within D k u v) : digraph_reach_within D k' u v
- Source
- monotonicity of digraph_reach_within, used for oriented_diameter_bound_holds_mono
- Verified
- 25 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 1
- digraph_reach_withindigraph_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…
- Used by 1
- 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)…
The proof, explained
The proof proceeds by induction on the inequality $k \le k'$ using the inductive definition of $\le$ on natural numbers. In the base case $k' = k$, the claim is immediate from the reachability hypothesis. In the successor step from $m$ to $m + 1$, reachability within $m$ steps implies reachability within $m + 1$ steps by taking the left disjunct in the recursive definition of reachability.
The claim holds in the base case where $k' = k$.
We induct on the relation $k \le k'$. In the base case $k' = k$, the goal is to show reachability within $k$ steps, which is given directly by the assumption $h$.
induction hk with | refl => exact h
If reachability holds within $m$ steps, it holds within $m + 1$ steps.
In the inductive step, the induction hypothesis ih states that $u$ reaches $v$ within $m$ steps. By definition, reaching $v$ within $m + 1$ steps is a disjunction whose first alternative is reachability within $m$ steps; applying Or.inl to ih completes the proof.
uses
Or.inl| step _ ih => exact Or.inl ih
Or.inl- From a proof of the first proposition $a$, infer the disjunction $a \lor b$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem digraph_reach_within_mono {V : Type*} (D : Digraph V) {k k' : ℕ} (hk : k ≤ k') (u v : V) (h : digraph_reach_within D k u v) : digraph_reach_within D k' u v := by induction hk with | refl => exact h | step _ ih => exact Or.inl ih