# Prove that $d[v_r] \le d[v_1] +1 ~and~ d[v_i] \le d[v_{i+1}], i=1,2, \cdots, r-1$ on queue $Q$ based on BFS algorithm

Given the following lemma first:

Lemma 1: Let $$G=$$ be a directed or undirected graph, and let $$s \in V$$ be an arbitrary vertex. Then, for any edge $$(u,v) \in E$$,

$$\lambda(s,v) \le \lambda(s,u) + 1\tag{1}\label{1}$$

I would like to discuss the following proof the following lemma:

Lemma 2: Suppose that during the execution of BFS on a graph $$G=$$, 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~ d[v_i] \le d[v_{i+1}], i=(1,2, \cdots, r-1) \tag{2} \label{2}$$

Definitions:

• $$d[v]$$ is the distance from source vertex $$v$$ to vertex $$u$$.
• BFS is breadth first search algorithm of a graph.
• $$\lambda(s,u)$$ is the shortest distance from $$s$$ to vertex $$u$$ as the minimum number of edges.

BFS Algorithm: (Courtesy to CLRS book):

Proof Lemma 2:

Basic step: By induction and for $$s$$ vertex only being in the queue, we can see that $$d[s] \le d[s] +1$$ and $$d[s] \le d[s]$$ holds.

Inductive step: (Courtesy to CLRS book)For the inductive step, we must prove the lemma holds after both dequeuing and enqueuing a vertex. If the head $$v_1$$ of the queue is dequeued, the new head is $$v_2$$. (If the queue becomes empty, then the lemma holds vacuously.) But then we have $$d[v_r] \le d[v_1] +1 \le d[v_2] + 1$$, and the remaining inequalities are unaffected. Thus, the lemma follows with $$v_2$$ as the head. Enqueuing a vertex requires closer examination of the code. In line 16 of BFS, when the vertex $$v$$ is enqueued, thus becoming $$v{r+1}$$, the head $$v_1$$ of $$Q$$ is in fact the vertex $$u$$ whose adjacency list is currently being scanned. Thus, $$d[v_{r+1}] = d[v] = d[u] + 1 = d[v_1] + 1$$. We also have $$d[v_r] \le d[v_1] + 1 = d[u] + 1 = d[v] = [v_{r+l}]$$, and the remaining inequalities are unaffected. Thus, the lemma follows when $$v$$ is enqueued.

Problem2:

1. We would like to prove that lemma 2 holds based on dequeuing and enqueuing of vertices to $$Q$$. If we don't remove any vertex from queue, then we would have complete list of vertices $$\left< v_1, v_2, \cdots, v_r \right>$$, so in this case and based on definition of distance $$d[v]$$, how we would have $$d[v_r] \le d[v_1] +1$$ in ref{2} please holds? I mean the distance to $$d[v_r]$$ is obviously as I see it can not be less than $$d[v_1] +1$$? $$v_r$$ is the last vertex added to queue and based on incrementing strategy in BFS, we would have $$d[v_r] = d[u] + 1$$, where $$u$$ is the precedence vertex as I see it, so I am not sure how this $$d[v_r] \le d[v_1] +1$$ hold please?
2. Same reasoning to the previous problem applies to this statement in the proof please," Thus, the lemma 2 follows with $$v_2$$ as the head." Same thing, it says that if we remove $$v_1$$, then $$d[v_r] \le d[v_2] + 1$$ as $$v_1$$ is removed now, but why this is the case again please same to issue/problem 1 I stated?