Ambiguity regarding the definition of 'path' in graph theory

Question

While going through the Introductory chapter of 'Graph Theory' by Bondy and Murty, I came across the definition of 'path' that says it's a sequence of vertices in such a way that two vertices are adjacent if they are consecutive in the sequence and non-adjacent otherwise.

However, on different sources I read that a path is just a sequence of vertices in such a way that two vertices are adjacent if consecutive and no vertex is repeated in the sequence.

I'm having trouble solving questions that involve the application of path. Kindly guide me through the correct definition of 'path' and why the definition is different in a standard text such as Bondy and Murty ?

Answer 1

Ahh, I think Bondy and Murty mean adjacent in the path if they are consecutive in the sequence, and non-adjacent otherwise. It's just their way of saying no vertex is repeated; if no vertex is repeated, then two vertices are adjacent in the sequence iff they are consecutive in the sequence. Conversely, if two vertices manage to be adjacent in a sequence without being consecutive in the sequence, that can only be because a vertex was repeated. (E.g., in the sequence $(a, b, c, d, b, e)$, the second and fourth elements are adjacent, despite being non-consecutive, only because $b$ is repeated.)

Frankly, I find the no-vertex-repeated statement more intuitive, but the definitions are identical.

Answer 2

The word path is often used in two different contexts:

1. A path graph is a graph consisting of a sequence of vertices such that two vertices are adjacent in the graph if and only if they are consecutive in the sequence. The notation $P_n$ is often used for a path graph of length $n$. This is what Bondy & Murty describe.

2. A path in a graph is a subgraph of a given graph that is isomorphic to a path graph. In other words, one might say there is a path in $G$ of length $n$, and by this we mean $P_n$ is a subgraph of $G$.

The word 'path' is used in both ways, but it's usually clear from context what is meant.