Definition:Path (Graph Theory)
Contents |
Definition
A path is a trail in which all vertices (except perhaps the first and last ones) are distinct.
A path between two vertices $u$ and $v$ is called a $u$-$v$ path.
The set of vertices and edges which go to make up a path form a subgraph.
This subgraph itself is also referred to as a path.
Open Path
An open path is a path in which the first and last vertices are distinct.
If the first and last vertices are the same, a path is called a cycle.
Comment
It seems at first glance that a path could also be defined as a walk in which all vertices are distinct.
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 $A \to B \to A$, for example, would fit the definition of a path, and therefore be a cycle, and this is not intended.
Hence the insistence that a path is a type of trail.
Differences in Terminology
Some sources call this a simple path, and use the term path to define what we have here as a walk.
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 2.3$
