Definition:Path (Graph Theory)/Also defined as
Jump to navigation
Jump to search
Path: Also defined as
Some sources define a path as:
By this definition it would appear that a path is automatically a trail, because if an edge were to be retraced in any walk, then the vertices at either end of it would necessarily be visited more than once.
However, under this looser definition, the walk $u \to v \to u$ for two adjacent vertices $u$ and $v$, for example, would fit the definition of a path, and therefore be a cycle.
But such a walk is not a trail, as the edge $u v$ would be traversed twice.
Hence, on $\mathsf{Pr} \infty \mathsf{fWiki}$, it is insisted that a path be defined as a type of trail.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 2.3$: Connected Graphs
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): path: 1.
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): walk
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): walk