Path (Graph Theory)
Calculus & Advanced MathA path in a graph is a sequence of vertices connected by edges where no vertex is repeated, representing a route through the graph.
Definition
A path in a graph is a route from one vertex to another that follows edges without revisiting any vertex. Think of it as a trail with no backtracking to a place you have already been.
Example
In a city map graph, a path from Home to School might go Home - Library - Park - School, visiting each place exactly once.
Key Insight
Finding the shortest path between two vertices is one of the most important problems in graph theory, solved by algorithms like Dijkstra's and Bellman-Ford.
Definition
A path is a sequence of distinct vertices $v_0, v_1, \ldots, v_k$ such that each consecutive pair $\{v_i, v_{i+1}\}$ is an edge. The length of the path is $k$ (number of edges). A closed path ($v_0 = v_k$) is a cycle. A graph is connected if a path exists between every pair of vertices.
Example
Graph with vertices $\{1,2,3,4\}$ and edges $\{12,23,34,14\}$: the path $1$-$2$-$3$-$4$ has length $3$. A Hamiltonian path visits every vertex exactly once; in this graph: $1$-$2$-$3$-$4$ is Hamiltonian.
Key Insight
Finding a Hamiltonian path (visiting all vertices once) is NP-complete in general, while finding an Eulerian path (traversing all edges once) is solvable in polynomial time. A subtle difference in problem statement leads to vastly different computational complexity.
Definition
The distance $d(u,v)$ in a graph is the length of the shortest path from $u$ to $v$. The diameter of $G$ is $\max_{u,v} d(u,v)$. The girth is the length of the shortest cycle. In weighted graphs, shortest paths are found by Dijkstra's (non-negative weights) or Bellman-Ford (negative weights allowed, detects negative cycles).
Example
The P vs. NP problem is closely connected to graph path problems: Hamiltonian path is NP-complete, but shortest path is in P. This dichotomy illustrates how slight changes in constraints dramatically alter algorithmic difficulty.
Key Insight
In algebraic graph theory, the number of walks of length $k$ from $u$ to $v$ equals the $(u,v)$ entry of $A^k$ (the $k$th power of the adjacency matrix), connecting path counting to linear algebra.