AFTD Auto-Formalizing Theoretical Domains

digraph_is_directed_path_singleton

theoremverified

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

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.

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

    line 4

    uses digraph_is_directed_path

      simp [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

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