Definition · applies to graphs (networks)

Elementary

Imagine a network drawn as dots joined by lines, like a map of cities and roads. A path is a route that goes from dot to dot along the lines and never visits the same dot twice.

Undergraduate (graph theory)

Consider a graph $G = (V, E)$. A path in $G$ is a sequence $v_0, v_1, \dots, v_k$ of distinct vertices such that each pair of consecutive vertices is joined by an edge:

\[\setdef{v_{i - 1}, v_i} \in E \quad \text{for } i = 1, 2, \dots, k.\]

The path starts at $v_0$ and ends at $v_k$. The length of the path is $k$, which is the number of edges that the path uses.

Examples

Examples

Non-examples
Things that may be mistaken for examples of this term.

Properties

  • A graph is connected if every two vertices of the graph are joined by a path.

Notes

A sequence of vertices joined by edges that may visit a vertex more than once is called a walk.

In topology, a path is a continuous function from $[0, 1]$ into a space, which is a different object; see continuous path vs. path in a graph.

Distinctions involving this term

  • Path: Continuous Path vs. Path in a Graph: “Path” has two common meanings, one in topology and one in graph theory. A continuous path is a continuous function $\gamma : [0, 1] \to X$ into a topological space $X$, so a continuous path passes through infinitely many points, unless the path stays at one point. A path in a graph is a finite sequence of distinct vertices such that each pair of consecutive vertices is joined by an edge.

All definitions · All distinctions · All examples