Hi, In this video, we're going to prove that the BFS returns correct distances, from A to all the nodes in the graph. The Lemma states that, when node u is discovered and put in the queue, distance to the node u is assigned exactly the correct distance from A to the node u in the graph, know that the only moment when dist of u is changed, is when the node u is discovered, but first, the distance to u is marked as infinity, and then as soon as it is discovered, the dist to u is updated, and we state that, this exact moment, dist of u is assigned to number which is equal to distance from A to the node u. To prove that, use mathematical induction, and as a base case, we consider the node A itself, when it is discovered, dist of A is assigned to exactly zero, which is the distance from A to itself. Assume that we've proved that the distance are correct for all the nodes at distance at most k from node A, and we're going to prove that for nodes at distance exactly k plus 1, this will be assigned to correct distance too. Consider any node v, which is actually a distance k plus 1 from node A, and we're going to prove that, this node will be updated with correct distance, when it is discovered. We know that it will be discovered, because all the reachable nodes will be discovered in the process of BFS, we proved that in the previous video, so when it is discovered, let's consider the node u, which is being processed while v is discovered. What can we say about this node u? We can say that the distance from a to node v, will be at most distance from A to node u plus 1, because, we can go from A to u, and then use the edge from u to v, and that would be a path from A to v, and from that it follows that the distance from a to the node u is at least k, because the distance from A to v is k plus 1, and we have this inequality, so distance from A to u is k or Beta. On the other hand, v is discovered after u is dequeued, and now we can use the order Lemma which we proved in the previous video, to say that the distance from A to v is strictly bigger than the distance from A to u. Why is that? Well, because if distance from A to v would be less than or equal to the distance from A to u, then v would be discovered before u is dequeued according to the ordinal level. This is not what happened, so distance from A to u is strictly less, than distance from A to v, which is equal to k plus 1 that we know, and now we know, the distance from A to u is simultaneously at least k and strictly less than k plus 1. We also know that this distance is an integer number, and there is only one integer number, which satisfies both inequalities and that is number k, so we know that the distance from A to u is exactly k, and this means, that when the dist of v is assigned, it is assigned to dist of u plus 1, and tat will be exactly k plus one, because when, distance to node u was assigned, we know by the assumption of the induction, that it was assigned the correct distance, and the correct distance is k, and dist of v, will be assigned exactly k plus 1, which is again correct distance, and this finishes our proof. This means actually that, the BFS algorithm finds correct distances, from node A to all the nodes because, at the moment when the node is discovered, it is already assigned correct distance, and after that, it is never enqueued and discovered again, so the distance stays correct, and for all the nodes, which are not reachable from A, we note that they won't be discovered at all, and so their distance will stay infinity, which is what we wanted.