# Ambiguity regarding the definition of 'path' in graph theory

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 ?

• Let me see if I understand this correctly. The way I read your paraphrase of the definition in Bondy and Murty, there is no path longer than two vertices in any complete graph $K_n$ where $n \geq 3$. Is that right? Commented Sep 1, 2015 at 21:22
• @BrianTung You can probably infer this from the definition of Bondy and Murty. Kindly refer to Page 4, last paragraph in the link bayanbox.ir/view/5987091202670485677/… Commented Sep 1, 2015 at 21:33
• Some authors will specify a simple path to mean that vertices never repeat along the path. When the problem under discussion is a shortest path (and edges are counted as positive length), then it follows that such shortest paths are inevitably simple, and no special qualification is necessary. Commented Sep 2, 2015 at 2:18

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$.
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.)