Reference no: EM131576751

Question: Show that if G is a directed graph and T is a spanning tree constructed using depth-first search, then G contains a circuit if and only if G contains a back edge (see Exercise) relative to the spanning tree T .

Exercise: Show that if G is a directed graph and T is a spanning tree constructed using depth-first search, then every edge not in the spanning tree is a forward edge connecting an ancestor to a descendant, a back edge connecting a descendant to an ancestor, or a cross edge connecting a vertex to a vertex in a previously visited sub tree.