$8\mathrm{.}6$ For the breadth$-$first search algorithm of Section $8\mathrm{.}5,$ prove the two statements

given on page $242.$ That is$,$ assuming we know the true shortest distance from a given

starting node $s$ in a network to all nodes at distance $d$ or less, and that the distance to

all other nodes has not yet been calculated, prove the following:

a$)$ For a node at distance $d,$ every neighbor that has not yet been assigned a distance

must have distance $d+1.$

b$)$ Every node at distance $d+1$ is a neighbor of at least one node with distance $d.$

Hint: While statement $1$ should be straightforward to prove, statement $2$ is a little more

involved. It may be useful to consider a path from $s$ to a node at distance $d+1,$ and then

consider the shortest distance from $s$ to the penultimate node along that path.