A depth$-$first forest classifies the edges of a graph into tree, back, forward, and

cross edges. A breadth$-$first tree can also be used to classify the edges reachable

from the source of the search into the same four categories.

a$.$ Prove that in a breadth$-$first search of an undirected graph, the following prop$-$

erties hold:

There are no back edges and no forward edges.

For each tree edge $(u,v),$ we have $v*d=u*d+1.$

For each cross edge $(u,v),$ we have $v*d=u*d$ or $v*d=u*d+1.$

b$.$ Prove that in a breadth$-$first search of a directed graph, the following properties

hold:

There are no forward edges.

For each tree edge $(u,v),$ we have $v*d=u*d+1.$

For each cross edge $(u,v),$ we have $v.du*d+1.$

For each back edge $(u,v),$ we have $0v.du.d.$