AFTD Auto-Formalizing Theoretical Domains

digraph_reach_within_mono

theoremverified

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.

  1. 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$.

    lines 3–4

      induction hk with
      | refl => exact h
  2. 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.

    line 5

    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

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