22.3.7 DFS-VISIT does not always result in a depth-first tree

[aetilley]

Consider the following graph that is G.V = {u, v, w}, G.E = {(u, v), (v, w), (u, w), (w, v)}

Consider what happens when we call DFS-VISIT(u):

A depth-first tree of this graph should be a linear order (either u->v->w or u->w->v). But the algorithm given in the solution will mark u as the parent of both v and w in the depth first tree.