Path (graph)

In graph theory, a path in a graph is a finite or infinite sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another. In a directed graph, a directed path (sometimes called dipath) is again a sequence of edges (or arcs) which connect a sequence of vertices, but with the added restriction that the edges all be directed in the same direction.

Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs.

A path is a trail in which all vertices (except possibly the first and last) are distinct. A trail is a walk in which all edges are distinct. A walk of length ${\displaystyle k}$ in a graph is an alternating sequence of vertices and edges, ${\displaystyle v_{0},e_{0},v_{1},e_{1},v_{2},\ldots ,v_{k-1},e_{k-1},v_{k}}$, which begins and ends with vertices. If the graph is undirected, then the endpoints of ${\displaystyle e_{i}}$ are ${\displaystyle v_{i}}$ and ${\displaystyle v_{i+1}}$. If the graph is directed, then ${\displaystyle e_{i}}$ is an arc from ${\displaystyle v_{i}}$ to ${\displaystyle v_{i+1}}$. An infinite path is an alternating sequence of the same type described here, but with no first or last vertex, and a semi-infinite path (also ray) has a first vertex, ${\displaystyle v_{0}}$, but no last vertex. Most authors require that all of the edges and vertices be distinct from one another. However, some authors do not make this requirement, and instead use the term simple path to refer to a path which contains no repeated vertices.

...
Wikipedia