Understanding CLRS BFT lemma

Question

I was reading BFT from CLRS. This is the example given in the book:

(Figure:The operation of BFS on an undirected graph. Tree edges are shown shaded as they are produced by BFS. The value of $u.d$ appears within each vertex $u$. The queue $Q$ is shown at the beginning of each iteration. Vertex distances appear below vertices in the queue.)

Then it gives following lemma:

Suppose that during the execution of BFS on a graph $G=(V,E)$, the queue $Q$ contains the vertices $<v_1,v_2,...,v_r>$, where $v_1$ is the head of $Q$ and $v_r$ is the tail. Then, $v_r.d\leq v_1.d+1$ and $v_i.d\leq v_{i+1}.d$ for $I=1,2,...,r-1$.

I am ok with $v_i.d\leq v_{i+1}.d$ for $I=1,2,...,r-1$ as I can observe this in all queue instances above. But I am not able to understand how $v_r.d\leq v_1.d+1$ aligns with above, as $i<i+1$, but $r>1$. How that $+1$ is making whole difference?

Answer 1

Suppose you have a tree like

        a           <-- level = 0
      / | \
     b  c  d        <-- level = 1
   /
  f                 <-- level = 2

    v1, v2, v3     
Q : b,  c,  d
    1,  1,  1

v3.d <= v1.d + 1   i.e 1 <= (1+1)

Now, suppose head of Q (i.e b) is removed and its neighbors are inserted in Q

    v1, v2, v3
Q : c,  d,  f
    1,  1,  2

v3.d <= v1.d + 1   i.e 2 <= (1+1)

This, v3.d <= v1.d + 1 can be also be seen as v3.d - v1.d <= 1 which means at any point of time distance between elements of queue will always be less than or equal 1. This can also be seen from the fact that during the execution of BFT only elements from 2 successive levels are present in queue. There cannot be case such that 2 elements A and B are present in queue with A at level x and B at level (x + 2).