# Path (graph theory)

In graph theory, a **path** is a walk, a sequence of vertices in which each consecutive pair is joined by an edge, in which no vertex is repeated; because vertices are distinct, no edge can be repeated either, so every path is also a trail.<sup>[1](https://mspace.lib.umanitoba.ca/bitstream/handle/1993/37010/GraphTheoryNotes2022.pdf)</sup><sup> • </sup><sup>[2](https://math.libretexts.org/Courses/SUNY_Geneseo/Math_104_Green/03%3A_Graph_Theory/3.05%3A_Navigating_Graphs)</sup> The path is the most restricted of the three basic traversal objects: every path is a trail, every trail is a walk, and a walk that revisits an edge is neither.<sup>[2](https://math.libretexts.org/Courses/SUNY_Geneseo/Math_104_Green/03%3A_Graph_Theory/3.05%3A_Navigating_Graphs)</sup>

| Key fact | Detail |
|---|---|
| Definition | A walk in which all vertices (and therefore all edges) are distinct<sup>[1](https://mspace.lib.umanitoba.ca/bitstream/handle/1993/37010/GraphTheoryNotes2022.pdf)</sup> |
| Hierarchy | All paths are trails (no repeated edges), and all trails are walks (no restrictions beyond staying on the graph)<sup>[2](https://math.libretexts.org/Courses/SUNY_Geneseo/Math_104_Green/03%3A_Graph_Theory/3.05%3A_Navigating_Graphs)</sup> |
| Length | The length of a path is the number of edges it traverses; a path of length k has k + 1 vertices<sup>[3](https://people.csail.mit.edu/meyer/mcs-diffs.pdf)</sup><sup> • </sup><sup>[1](https://mspace.lib.umanitoba.ca/bitstream/handle/1993/37010/GraphTheoryNotes2022.pdf)</sup> |
| Notation | A path of length k is denoted \( P_k \) for \( k \ge 2 \); some texts instead use \( P_{k+1} \), counting vertices<sup>[1](https://mspace.lib.umanitoba.ca/bitstream/handle/1993/37010/GraphTheoryNotes2022.pdf)</sup> |
| Connectivity | A graph is connected if, for any two distinct vertices, there is a path between them<sup>[4](https://notes.bweston.uk/comp202/)</sup> |
| Distance | The distance \( d(x,y) \) between two vertices in a connected graph is the length of a shortest x–y path<sup>[1](https://mspace.lib.umanitoba.ca/bitstream/handle/1993/37010/GraphTheoryNotes2022.pdf)</sup> |
| Terminology caveat | Definitions vary between texts: some authors call walks "paths" and reserve "simple path" for the no-repeats version<sup>[3](https://people.csail.mit.edu/meyer/mcs-diffs.pdf)</sup> |

## Walks, trails, and paths

A **walk** in a graph \( G = (V, E) \) is an alternating sequence of vertices and edges \( v_0, e_1, v_1, \ldots, e_m, v_m \) with \( e_i = \{v_{i-1}, v_i\} \in E \); vertices and edges may repeat. In a simple graph, where there are no parallel or multiple edges, the edges are implied by the vertex sequence, so a walk can be written as a list of vertices alone.<sup>[5](https://www.cs.cmu.edu/afs/cs/academic/class/15210-f15/www/tapp.html)</sup> A **trail** is a walk with no edge repeated, though vertices may repeat; a **path** is a walk with no vertex repeated.<sup>[1](https://mspace.lib.umanitoba.ca/bitstream/handle/1993/37010/GraphTheoryNotes2022.pdf)</sup>

The restrictions nest. On a six-vertex graph with edges a–b, b–c, b–d, a–d, a–e, d–e, and e–f, the walk (a, b, d, a, b, c) is neither a trail nor a path because it repeats edges and vertices; the walk (a, d, e, a, b, c) is a trail but not a path because vertex a recurs; the walk (a, e, d, b, c) is a path and hence also a trail.<sup>[6](https://cnds.constructor.university/courses/mfcs-2025/mfcs-notes.pdf)</sup>

A walk is **closed** when its first and last vertices coincide. A closed trail is called a **circuit**, and a circuit with no repeated intermediate vertices is a **cycle**; equivalently, a cycle is a closed walk in which only the first and last vertex are the same.<sup>[7](https://www.isibang.ac.in/~d.yogesh/Course_Notes/DM1/Ch2.S3.html)</sup><sup> • </sup><sup>[1](https://mspace.lib.umanitoba.ca/bitstream/handle/1993/37010/GraphTheoryNotes2022.pdf)</sup>

## Terminology varies by source

The words are not standardized across the literature. The MIT text *Mathematics for Computer Science* defines a "path" as what most graph theory texts call a walk, and a "simple path" as what they call a path, adding an explicit warning to readers about the shift.<sup>[3](https://people.csail.mit.edu/meyer/mcs-diffs.pdf)</sup> Stanford's CS106B notes the same split: some sources require a path to have no repeated vertices, while others allow repeats and use "simple path" for the no-repeats version; some sources also define a path as a list of edges rather than vertices.<sup>[8](https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1242/lectures/26-graphs/)</sup> A LibreTexts discrete mathematics text advises readers to always check the definitions in the material they are reading, since the terms vary widely, including being reversed.<sup>[9](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_for_Computer_Science_%28Fitch%29/05%3A_Graph_Theory/5.04%3A_Paths)</sup> The no-repeats version is also called a **simple path** or a **self-avoiding walk**.<sup>[7](https://www.isibang.ac.in/~d.yogesh/Course_Notes/DM1/Ch2.S3.html)</sup>

## Reduction to paths

Paths matter because walks can always be cleaned into them. For distinct vertices u and v, a walk from u to v exists if and only if a trail exists if and only if a path exists: given any walk, a repeated vertex x splits it into segments, and deleting the segment between the first and last appearance of x produces a shorter walk; iterating this loop-removal ends at a path.<sup>[7](https://www.isibang.ac.in/~d.yogesh/Course_Notes/DM1/Ch2.S3.html)</sup> This is why connectivity can be defined with walks or paths interchangeably, and why a graph is connected exactly when every pair of distinct vertices has a path between them.<sup>[4](https://notes.bweston.uk/comp202/)</sup>

## The path graph

The **path graph** \( P_n \) is a tree on \( n \ge 2 \) vertices with two nodes of degree 1 and \( n - 2 \) nodes of degree 2; it can be drawn with all vertices and edges on a single straight line.<sup>[10](https://mathworld.wolfram.com/PathGraph.html)</sup> The single-vertex case \( P_1 \) is the singleton graph, equivalent to the complete graph \( K_1 \).<sup>[10](https://mathworld.wolfram.com/PathGraph.html)</sup>

## Paths in algorithmic problems

Several central computational problems are stated in terms of paths. The **shortest-path problem** asks for a path of minimum cost between two vertices; a survey of the area classifies algorithms along dimensions such as single-source versus all-pairs, static versus dynamic graphs, and exact versus approximate answers, and notes that no single algorithm covers all variants.<sup>[11](https://arxiv.org/abs/1705.02044)</sup> [Edsger W. Dijkstra](https://www.edgepedia.org/edsger-w-dijkstra), a Dutch computer scientist, published the original shortest-path algorithm in *Numerische Mathematik* in 1959, restricting attention to graphs in which at least one path exists between any two nodes.<sup>[12](https://www.cs.yale.edu/homes/lans/readings/routing/dijkstra-routing-1959.pdf)</sup>

The **longest path problem** asks for a simple path of maximum length in a given graph, and it is NP-hard; a greedy approximation algorithm for undirected graphs runs in \( O(n^2(n+m)) \) time on n vertices and m edges.<sup>[13](https://arxiv.org/abs/1209.2503)</sup>

Two classical special paths carry names. An **Eulerian trail** uses every edge of a graph exactly once; [Leonhard Euler](https://www.edgepedia.org/leonhard-euler)'s 1736 solution of the [Seven Bridges of Königsberg](https://www.edgepedia.org/seven-bridges-of-konigsberg) problem showed that such a traversal exists exactly when the graph has either zero or exactly two vertices of odd degree, and his paper is often cited as the first example of graph theory.<sup>[14](https://mathshistory.st-andrews.ac.uk/HistTopics/Topology_in_mathematics/)</sup> A **Hamiltonian path** visits every vertex exactly once; [William Rowan Hamilton](https://www.edgepedia.org/william-rowan-hamilton), the Irish mathematician, invented the Icosian Calculus in 1856 to investigate closed edge paths on a dodecahedron that visit each vertex exactly once, and presented the associated Icosian Game at the 1857 meeting of the British Association in Dublin; such closed edge paths in general graphs are today known as Hamiltonian circuits.<sup>[15](https://www.maths.tcd.ie/pub/HistMath/People/Hamilton/Icosian/)</sup>

## References

1. [Graph Theory Notes 2022, University of Manitoba](https://mspace.lib.umanitoba.ca/bitstream/handle/1993/37010/GraphTheoryNotes2022.pdf)
2. [Navigating Graphs, Mathematics LibreTexts](https://math.libretexts.org/Courses/SUNY_Geneseo/Math_104_Green/03%3A_Graph_Theory/3.05%3A_Navigating_Graphs)
3. [Chapter 9, Simple Graphs, Mathematics for Computer Science (Meyer, MIT)](https://people.csail.mit.edu/meyer/mcs-diffs.pdf)
4. [COMP202 Complexity of Algorithms notes, University of Liverpool](https://notes.bweston.uk/comp202/)
5. [Parallel Computing: Theory and Practice, Chapter 15, Carnegie Mellon University](https://www.cs.cmu.edu/afs/cs/academic/class/15210-f15/www/tapp.html)
6. [Walks, Trails, Paths, MFCS notes, Constructor University](https://cnds.constructor.university/courses/mfcs-2025/mfcs-notes.pdf)
7. [Walks, Trails and Paths, Discrete Mathematics lecture notes, ISI Bangalore](https://www.isibang.ac.in/~d.yogesh/Course_Notes/DM1/Ch2.S3.html)
8. [CS106B Graph Algorithms, Stanford University](https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1242/lectures/26-graphs/)
9. [Paths, Discrete Mathematics for Computer Science, Mathematics LibreTexts](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_for_Computer_Science_%28Fitch%29/05%3A_Graph_Theory/5.04%3A_Paths)
10. [Path Graph, Wolfram MathWorld](https://mathworld.wolfram.com/PathGraph.html)
11. [A Survey of Shortest-Path Algorithms (Madkour et al., arXiv)](https://arxiv.org/abs/1705.02044)
12. [E. W. Dijkstra (1959), A note on two problems in connexion with graphs, Numerische Mathematik 1, 269–271](https://www.cs.yale.edu/homes/lans/readings/routing/dijkstra-routing-1959.pdf)
13. [A greedy approximation algorithm for the longest path problem in undirected graphs (arXiv)](https://arxiv.org/abs/1209.2503)
14. [Topology history, MacTutor History of Mathematics, University of St Andrews](https://mathshistory.st-andrews.ac.uk/HistTopics/Topology_in_mathematics/)
15. [The Icosian Calculus, William R. Hamilton, Trinity College Dublin](https://www.maths.tcd.ie/pub/HistMath/People/Hamilton/Icosian/)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph theory overview and basic objects*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license