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 properties 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.$