AFTD Auto-Formalizing Theoretical Domains

digraph_reach_within_one_of_adj

theoremverified

Sanity: an arc u -> v is a directed walk of length at most 1 from u to v.

Statement

theorem digraph_reach_within_one_of_adj {V : Type*} (D : Digraph V) (u v : V) (h : D.Adj u v) :
    digraph_reach_within D 1 u v
Source
sanity lemma for digraph_reach_within
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…

The proof, explained

The proof unfolds the inductive definition of reachability within 1 step, which holds if either u = v or there exists an intermediate vertex w adjacent to u from which v is reachable in 0 steps. Taking w = v, the edge hypothesis h and reflexivity satisfy the existential condition in the right-hand disjunct.

  1. v is reachable from u within 1 step in D

    By the recursive definition of reachability within k + 1 steps, reachability within 1 step means either reachability in 0 steps (u = v) or the existence of a vertex w such that D.Adj u w and v is reachable from w in 0 steps (w = v). Using Or.inr to select the second disjunct, the vertex v itself serves as the witness w: the hypothesis h provides the adjacency D.Adj u v, and reflexivity (rfl) confirms that v = v.

    line 2

    uses Or.inr

        digraph_reach_within D 1 u v := Or.inr ⟨v, h, rfl⟩
Or.inr
From a proof of b, infer the disjunction a ∨ b.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). 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_one_of_adj {V : Type*} (D : Digraph V) (u v : V) (h : D.Adj u v) :    digraph_reach_within D 1 u v := Or.inr ⟨v, h, rfl⟩
See it in the graphDiscuss this resultChallenge it