AFTD Auto-Formalizing Theoretical Domains

digraph_two_path_count

def

The number of directed paths of length two from u to v in a finite directed graph D, defined as the number of vertices w such that D has an arc from u to w and an arc from w to v.

Statement

def digraph_two_path_count {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (u v : V) : ℕ
Defined in
arXiv:2610.39702, Section 2.1
Verified
30 Oct 2026
Axioms
none listed
Used by 3

Read back from the Lean

Given a finite type V, a directed graph D : Digraph V with decidable adjacency relation D.Adj, and vertices u, v : V, digraph_two_path_count D u v is defined as the number (cardinality) of vertices w : V such that there is a directed edge from u to w (D.Adj u w) and a directed edge from w to v (D.Adj w v).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The number of directed paths of length two from u to v in a finite directed graph. -/
def digraph_two_path_count {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (u v : V) : ℕ := (Finset.univ.filter (fun w => D.Adj u w ∧ D.Adj w v)).card
See it in the graphDiscuss this resultChallenge it