Question 55

1. In an unweighted undirected graph $G$, the BFS tree $T$ rooted at $s$ partitions the vertices into levels $L_0, L_1, L_2, \dots$, where level $L_k$ contains all vertices at shortest distance $d(x) = k$ from $s$.

2. For every edge $(u, v) \in E(G)$:
   Since there is a direct edge connecting $u$ and $v$, the shortest path distance from $s$ satisfies the triangle inequality:

   $$d(u) \le d(v) + 1 \quad \text{and} \quad d(v) \le d(u) + 1.$$

   This implies:

   $$-1 \le d(u) - d(v) \le 1.$$

3. Therefore, for any non-tree edge $(u, v)$:

   • If $u$ and $v$ are in the same level, $d(u) - d(v) = 0$.
   • If $u$ is in level $k$ and $v$ is in level $k+1$, $d(u) - d(v) = -1$.
   • If $u$ is in level $k+1$ and $v$ is in level $k$, $d(u) - d(v) = 1$.

4. An edge cannot connect vertices whose levels differ by 2 or more, because if $d(u) - d(v) = 2$, then $d(u) = d(v) + 2$. However, following the edge from $v$ would give a path of length $d(v) + 1$ to $u$, contradicting that $d(u) = d(v) + 2$.

Thus, $d(u) - d(v)$ CANNOT be $2$ (option D).