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
- tournament_strong_king_iff_in_neighbor_out_degree_leIn any finite tournament T, a vertex v is a strong king if and only if every in-neighbor u of v (that is, every vertex u with an arc from…
- tournament_two_path_diff_eq_out_degree_diffIn any finite tournament T, if there is an arc from u to v, then the difference between the number of directed two-paths from v to u and…
- tournament_is_strong_kingA vertex v in a finite directed graph D is a strong king if for every in-neighbor u of v (that is, every vertex u with an arc from u to…
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