Graph Path — Definition, Formula & Examples

A graph path is a sequence of distinct vertices where each consecutive pair is connected by an edge. It describes a route through a graph that never revisits a vertex.

In a graph $G = (V, E)$ , a path is a finite sequence of vertices $v_0, v_1, v_2, \ldots, v_k$ such that each $v_i$ is distinct and $(v_{i-1}, v_i) \in E$ for all $i \in \{1, 2, \ldots, k\}$ . The number of edges $k$ is called the length of the path.

How It Works

To find a path between two vertices, start at one vertex and follow edges to adjacent vertices without revisiting any vertex you have already used. If you reach the target vertex, the sequence of vertices you visited forms a path. The length of that path equals the number of edges traversed, not the number of vertices. A shortest path between two vertices has the minimum possible length among all paths connecting them.

Worked Example

Problem: Consider a graph with vertices {A, B, C, D, E} and edges {AB, BC, CD, BE, DE}. Find a path from A to D and state its length.

Step 1: Start at vertex A. The only neighbor of A is B, so move to B.

A \to B

Step 2: From B, you can go to C or E. Choose E.

A \to B \to E

Step 3: From E, the neighbor D has not been visited. Move to D.

A \to B \to E \to D

Answer: One path from A to D is A → B → E → D, which has length 3 (three edges). Another valid path is A → B → C → D with the same length.

Why It Matters

Paths are the basis for algorithms like Dijkstra's shortest path and breadth-first search, which power GPS navigation and network routing. In computer science courses, understanding paths is essential before studying trees, cycles, and graph connectivity.

Common Mistakes

Mistake: Confusing a path with a walk or trail by allowing repeated vertices.

Correction: A path requires all vertices to be distinct. A walk allows repeated vertices and edges, while a trail allows repeated vertices but not repeated edges. If any vertex appears twice, it is not a path.