Page 292 Exercise 13

Ihave 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 the BFS.  Assume for the purpose of the discussion that follows that v = v₀, u = v₁, w= v₇, and x = v₄. 

Recall that BFS begins with some vertex v.  This vertex is marked as visited, and the search continues with v's adjacency list. Each vertex on v's adjacency list (u₀..u_n-1) is marked as visited, and placed on a queue.  The initial vertex (v) is the root of the tree.  Each of its adjacent vertices must be tree edges unless the graph contains self-loops.  The algorithm removes a vertex (u₀) from the queue, and examines each of its adjacent
vertices. If the adjacent vertex is unvisited, it is marked as visited, and it is  placed on the queue.  Since unvisited vertices lead to new edges, they are tree edges.  However,  assume that at  some point in the traversal we begin examining vertex w's adjacency list, and discover the edge (w,x) where x is a previously visited vertex.  Because x is an ancestor of w, it is a back edge. Since these edges are ignored by the algorithm, the completed
traversal must include only tree edges.