Path in a Graph
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
-
✓ The vertex sequence $a, b, a$ in the triangle graph with vertices $a$, $b$, $c$ and edges $\setdef{a, b}$, $\setdef{b, c}$, $\setdef{c, a}$ UndergraduateThe vertex sequence $a, b, a$ is not a path in the triangle graph, because $a, b, a$ visits the vertex $a$ twice; a sequence of vertices joined by edges that may repeat vertices is called a walk.
-
✓ The vertex sequence $a, b, c$ in the triangle graph with vertices $a$, $b$, $c$ and edges $\setdef{a, b}$, $\setdef{b, c}$, $\setdef{c, a}$ UndergraduateThe vertex sequence $a, b, c$ is a path from $a$ to $c$ in the triangle graph, because the vertices $a$, $b$, $c$ are distinct and the edges $\setdef{a, b}$ and $\setdef{b, c}$ join consecutive vertices.
Non-examplesThings that may be mistaken for examples of this term.
-
The half circle $\gamma$ is not a path in a graph, because $\gamma$ is a function on the interval $[0, 1]$, not a sequence of vertices of a graph.
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.