digraph_is_directed_path_singleton
For every digraph D and vertex v, the singleton list [v] is a directed path from v to v.
Statement
theorem digraph_is_directed_path_singleton {V : Type*} (D : Digraph V) (v : V) : digraph_is_directed_path D [v] v v
- Source
- folklore
- Verified
- 29 Oct 2026
- Axioms
propext- Built on 1
- digraph_is_directed_pathA directed path from u to v in a digraph D is a list of vertices p forming a directed chain in D with no duplicate vertices, starting at u…
- Used by 1
- digraph_finite_sink_strong_subgraphEvery nonempty finite vertex set contains a nonempty strongly connected subset with no outgoing arc to the rest of that set.
Read back from the Lean
For any type V, any directed graph D on V, and any vertex v : V, the singleton list [v] is a directed path in D from v to v.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
A singleton list [v] trivially satisfies the definition of a directed path from v to v. By definition, a directed path requires consecutive vertices to be adjacent, all vertices to be distinct, and the path to start and end at the specified endpoints. For a single-vertex path, the adjacency requirement is vacuous, no vertices are repeated, and the start and end are both v, so simplification immediately closes the goal.
The singleton list [v] is a directed path from v to v in D.
Unfolding the definition of `digraph_is_directed_path` for the list [v] requires verifying four conditions: the consecutive elements are adjacent (`[v].IsChain D.Adj`), there are no duplicate elements (`[v].Nodup`), the first element is v (`[v].head? = some v`), and the last element is v (`[v].getLast? = some v`). For a list of length 1, adjacency is vacuously true, there are no duplicates, and both the head and the last element are v. The `simp` tactic unfolds the definition and simplifies each condition to `True`.
uses
digraph_is_directed_pathsimp [digraph_is_directed_path]
digraph_is_directed_path- A list of vertices forms a directed path from u to v in a digraph if consecutive vertices are connected by directed edges, all vertices in the list are distinct, the first vertex is u, and the last vertex is v.
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.
/-- The singleton list [v] is a directed path from v to v in any digraph. -/theorem digraph_is_directed_path_singleton {V : Type*} (D : Digraph V) (v : V) : digraph_is_directed_path D [v] v v := by simp [digraph_is_directed_path]