Explain why all nontree edges are cross edges, with respect to a BFS tree constructed for an undirected graph.   Explain why there are no forward nontree edges with respect to a BFS tree constructed...

Explain why all nontree edges are cross edges, with respect to a BFS tree

constructed for an undirected graph.

Explain why there are no forward nontree edges with respect to a BFS tree

constructed for a directed graph.

Show that if
T
is a BFS tree produced for a connected graph
G, then, for

each vertex
v
at level
i, the path of
T
between
s
and
v
has
i
edges, and any

other path of
G
between
s
and
v
has at least
i
edges.

Justify Proposition 14.16.