@leslietownes. **Lemma 2**: Suppose that during the execution of **BFS** on a graph $G=<V,E>$, the queue $Q$
contains the vertices $\left< v_1, v_2, \cdots, v_r \right>$, where $v_1$ is the head of $Q$ and $v_r$ is the tail. Then, $d[v_r] \le d[v_1] +1 $ and C 1 and $d[v_i] \le d[v_{i+1}]$ for $i=1,2, \cdots, r-1$.