Directed Paths

Definition

Let $(V, E)$ be a directed graph. A directed path between vertex $v$ and vertex $w \neq v$ is a finite sequence of distinct vertices, whose first coordinate is $v$ and whose last coordinate is $w$, and whose consecutive coordinates (as ordered pairs) are edges in the graph. We say that a path between $v$ and $w$ is from $v$ to $w$. The length of the path is one less than the number of vertices: namely, the number of edges.

Two vertices are connected in a graph if there exists at least one path between them. A directed graph is connected if there is a path between every pair of vertices. A graph is acyclic if none of its paths cycle.

Other terminology

Some authors allow paths to contain repeated vertices, and call a path with distinct vertices a simple path. Similarly, some authors allow a cycle to contain repeated vertices, and call a path with distinct vertices a simple cycle or circuit. Some authors use the term loop instead of cycle.