GATE CS 2015 Set 1 Q45 — Graph Traversals (BFS, DFS)

In an unweighted, undirected graph $G = (V, E)$, the shortest distance $d(x)$ from a source vertex $s$ to any vertex $x$ is the minimum number of edges on a path between them.

For any edge $(u, v) ext{ in } E$ (regardless of whether it is selected in the BFS tree $T$ or not), the triangle inequality for shortest path distances must hold:

1. The shortest path to $u$ cannot be longer than the shortest path to $v$ plus the edge $(u, v)$: $$d(u) \le d(v) + 1 \implies d(u) - d(v) \le 1$$
2. Similarly, the shortest path to $v$ cannot be longer than the shortest path to $u$ plus the edge $(u, v)$: $$d(v) \le d(u) + 1 \implies d(u) - d(v) \ge -1$$

Combining these two inequalities, we get:

Since the distance function $d(x)$ only takes non-negative integer values, the only possible values for $d(u) - d(v)$ are $-1$, $0$, and $1$.

Therefore, $d(u) - d(v)$ CANNOT be $2$.