digraph_is_directed_path
A 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 and ending at v.
Statement
def digraph_is_directed_path {V : Type*} (D : Digraph V) (p : List V) (u v : V) : Prop
- Defined in
- Bang-Jensen and Gutin, Digraphs: Theory, Algorithms and Applications, 2009
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 20
- not_digraph_ckk_subdivision_three_exceptionalThe statement
digraph_ckk_subdivision_three_exceptionalis false: The statement omits any nonemptiness hypothesis on the vertex type, so… - digraph_17_shared_target_forces_two_cyclesThe normalized oriented seventeen-vertex shared-target configuration with three designated parents contains two disjoint cycles, assuming…
- digraph_common_cycle_core_neighbor_uniqueInside a strongly connected finite set, if every directed cycle contains a fixed core, every vertex has at most one outgoing neighbor and…
- digraph_four_strong_tournament_unilaterally_two_linkedLet D be a digraph on a finite type V. If D is a tournament and D is 4-strong, then D is unilaterally 2-linked.
- linkage_of_common_neighborIn a 4-strong digraph D, if v is outside {s₁, t₁, s₂, t₂} and (s₁ → v → t₁) or (t₁ → v → s₁), then unilateral 2-linkage exists for {s₁,…
- digraph_is_k_strongA finite digraph D is k-strong (k-strongly connected) if its vertex count exceeds k and for every vertex subset s of cardinality strictly…
- digraph_five_strong_short_path_avoiding_finsetLet D be 5-strong, A₀ a set of at most 2 vertices and T a set of fewer than 3 vertices. Then any two distinct vertices outside T ∪ A₀ are…
- digraph_is_two_linkedA digraph D is 2-linked if for every four pairwise distinct vertices s₁, t₁, s₂, t₂ in D, there exist vertex-disjoint directed paths from…
- digraph_is_directed_path_singletonFor every digraph D and vertex v, the singleton list [v] is a directed path from v to v.
- digraph_four_strong_semicomplete_multipartite_adjacent_pair_linkedLet D be a 4-strong semicomplete multipartite digraph on a finite type V. If s₁, t₁, s₂, t₂ are pairwise distinct vertices of D such that…
- 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.
- digraph_exists_four_strong_semicomplete_multipartite_not_unilaterally_two_linked_eightThere exists a finite type V with exactly 8 elements and a digraph D on V such that D is 4-strong, semicomplete multipartite, and not…
- digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked_rightLet D be a 4-strong semicomplete multipartite digraph. If s₁, t₁, s₂, t₂ are pairwise distinct vertices such that there is an arc between…
- digraph_unilaterally_two_linked_of_two_linkedEvery 2-linked digraph is unilaterally 2-linked.
- digraph_16_shared_target_forces_two_cyclesThe normalized oriented sixteen-vertex shared-target configuration contains two disjoint cycles, assuming the displayed two-cycle criterion.
- digraph_common_cycle_core_outside_injectionIn a strongly connected finite vertex set, suppose all directed cycles contain a core K and every vertex in a subset S of K has at least…
- digraph_has_ckk_subdivisionA digraph D contains a subdivision of C(k,k) if there exist two distinct vertices u, v and two internally vertex-disjoint directed paths…
- short_path_gives_linkage_four_strongIn a 4-strong digraph D, if there is a directed path between {s₁, t₁} with at most 3 vertices that avoids {s₂, t₂}, then there exist…
- digraph_is_unilaterally_two_linkedA digraph D is unilaterally 2-linked if for every four pairwise distinct vertices s₁, t₁, s₂, t₂ in D, there exist vertex-disjoint…
- linkage_of_common_neighbor_rightIn a 4-strong digraph D, if v is outside {s₁, t₁, s₂, t₂} and (s₂ → v → t₂) or (t₂ → v → s₂), then unilateral 2-linkage exists for {s₁,…
- not_digraph_ckk_subdivision_three_exceptionalThe statement
Read back from the Lean
For a vertex type V, a directed graph D : Digraph V, a list of vertices p : List V, and vertices u, v : V, digraph_is_directed_path D p u v defines the proposition that p is a simple (non-self-intersecting) directed path from u to v in D. That is, all of the following hold:
1. p.IsChain D.Adj: for every pair of consecutive elements x then y in the list p, there is a directed edge from x to y (D.Adj x y);
2. p.Nodup: all vertices in p are pairwise distinct (no vertex is visited more than once);
3. p.head? = some u: the first element of p is u (in particular, p is non-empty);
4. p.getLast? = some v: the last element of p is 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
/-- A directed path in a digraph D is a nodup chain of directed edges from u to v. -/ def digraph_is_directed_path {V : Type*} (D : Digraph V) (p : List V) (u v : V) : Prop := p.IsChain D.Adj ∧ p.Nodup ∧ p.head? = some u ∧ p.getLast? = some v