Page 292 Exercise 12

I have redrawn (below) Figure 6.16(a) with the tree edges in solid black lines , and the back edges in solid green lines. This graph illustrates the results of a depth first traversal.  Assume for the purpose of the discussion that follows that v = V₀, u = v₁, and w = v₂. 

Recall that a depth first search begins with some vertex v.  This vertex is marked as visited, and the search continues with v's adjacency list.  Assume that an unvisited vertex u is found.  The edge (v,u) is a tree edge because it connects a vertex in the tree (v) with an unvisited vertex (u).  Because u is not currently in the tree, its introduction cannot create a cycle.  The traversal now continues with u's adjacency list.  Assume that at some
point in our traversal we examine vertex w's adjacency list, and discover that vertex u is on it.   Edge (w,u) is a back edge because u appears higher in the tree than w.  Adding the edge (w,u) to the tree would produce a cycle, as the diagram above illustrates.  The algorithm prevents the introduction of back edges by marking ancestors as visited.  Since edges that contain previously visited vertices are ignored, the algorithm excludes
cycles.