digraph_reach_within_one_of_adj
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.
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.
uses
Or.inrdigraph_reach_within D 1 u v := Or.inr ⟨v, h, rfl⟩
Or.inr- From a proof of b, infer the disjunction a ∨ b.
- By definition, 1-step reachability `digraph_reach_within D 1 u v` unfolds to `digraph_reach_within D 0 u v ∨ ∃ w, D.Adj u w ∧ digraph_reach_within D 0 w v`, and 0-step reachability is definitionally equality. The proof provides the right-hand alternative directly in term mode.
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⟩