Graph Path
A path in a graph is a sequence of vertices in which each consecutive pair is connected by an edge and no vertex is repeated. The length of a path is defined as the number of edges it traverses. Paths are central to graph algorithms such as Dijkstra's shortest-path algorithm, breadth-first search, and depth-first search, which are used in navigation systems, network routing, and AI planning.
Key Formula
A path P is a sequence of distinct vertices v₀, v₁, ..., vₖ where each consecutive pair shares an edge
LaTeX: P = v_0, v_1, v_2, \ldots, v_k \text{ where } (v_{i-1}, v_i) \in E \text{ and all } v_i \text{ distinct}
| Symbol | Meaning | Unit |
|---|---|---|
| vᵢ | The i-th vertex in the path sequence | none |
| k | Length of the path (number of edges) | none |
| E | Edge set of the graph | none |
Worked Example
Problem
In a graph with vertices {A, B, C, D, E} and edges {AB, BC, CD, DE, AC, BE}, find all simple paths from A to E of length ≤ 3.
Solution
Step 1: List edges: AB, BC, CD, DE, AC, BE. Step 2: Explore paths from A to E (no repeated vertices): Path 1: A → B → E (length 2, uses edges AB, BE) ✓ Path 2: A → C → D → E (length 3, uses AC, CD, DE) ✓ [Wait: is CE an edge? No.] Path 3: A → B → C → D → E (length 4 — exceeds limit, skip) Step 3: Check A → C → ... → E: AC then no direct CE; would need C→D→E (total A→C→D→E = length 3) ✓ Step 4: List valid paths of length ≤ 3: [A,B,E] and [A,C,D,E].
Answer
Two simple paths from A to E of length ≤ 3: A→B→E (length 2) and A→C→D→E (length 3).
Path-Related Concepts in Graph Theory
| Concept | Definition | Vertices Repeated? | Edges Repeated? |
|---|---|---|---|
| Walk | Any sequence of vertices connected by edges | Yes | Yes |
| Trail | Walk with no repeated edges | Yes | No |
| Path | Walk with no repeated vertices (or edges) | No | No |
| Cycle | Path that starts and ends at the same vertex | No (except endpoints) | No |
| Euler Path | Trail that visits every edge exactly once | Yes | No |
| Hamiltonian Path | Path that visits every vertex exactly once | No | No |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Euler Path
An Euler path (or Eulerian path) is a trail in a graph that visits every edge exactly once, without necessarily returning to the starting vertex. An Euler circuit (or Eulerian circuit) is an Euler path that begins and ends at the same vertex. A connected graph has an Euler path if and only if it has exactly zero or two vertices of odd degree; if two odd-degree vertices exist, the path must start and end at those vertices.
Hamiltonian Cycle
A Hamiltonian cycle (or Hamiltonian circuit) is a closed path in a graph that visits every vertex exactly once before returning to the starting vertex. Unlike the Euler path (which covers every edge), the Hamiltonian cycle covers every vertex. Determining whether a Hamiltonian cycle exists in an arbitrary graph is an NP-complete problem, making it one of the central challenges in computational complexity and combinatorial optimisation (e.g., the Travelling Salesman Problem).
Graph Theory
Graph theory is the branch of mathematics that studies graphs — mathematical structures consisting of vertices (nodes) connected by edges (links) used to model pairwise relationships between objects. It was founded by Leonhard Euler in 1736 when he solved the Königsberg bridge problem. Graph theory underpins computer networks, social network analysis, circuit design, scheduling algorithms, and shortest-path computations.
The word "path" in mathematics retains its everyday English meaning of a route between two points. In graph theory, its precise definition excluding repeated vertices was established in the foundational work of König (Theorie der endlichen und unendlichen Graphen, 1936) and further codified by Berge in the 1950s.