Forward Edge in an Undirected Graph

Question

CLRS - Chapter 22

Theorem 22.10

In a depth-first search of an undirected graph G, every edge of G is either a tree edge or a back edge.

Proof Let (u,v) be an arbitrary edge of G, and suppose without loss of generality that u.d < v.d. Then the search must discover and finish v before it finishes u (while u is gray), since v is on u’s adjacency list. If the first time that the search explores edge (u,v), it is in the direction from u to v, then v is undiscovered (white) until that time, for otherwise the search would have explored this edge already in the direction from v to u. Thus, (u.v) becomes a tree edge. If the search explores (u,v) first in the direction from v to u, then (u,v) is a back edge, since u is still gray at the time the edge is first explored.

I most certainly understand the proof; but not quite convinced with the idea of forward edges.

In the above image, there is a forward edge from the first vertex to the third vertex (first row). The first vertex is the source.

As I understand DFS(S) would include a forward vertex 1 -> 3. (I am obviously wrong, but I need somebody to set me straight!)

Answer 1

It looks like you didn't include the definition of "forward edge," so I'll start with the definition I learned.

Assuming u.d < v.d, DFS labels the edge (u,v) a forward edge if when crossing the edge from u to v, v has already been marked as visited.

Because of that though, I claim that you cannot have forward edges in an undirected graph.

Assume for the sake of contradiction that it was possible. Therefore, the destination node is already marked as visited. Thus, DFS has already gone there and crossed all of the adjacent edges. In particular, you had to have already crossed that edge in the opposite direction. Thus, the edge has already been marked as a certain type of edge and thus won't be marked as a "forward edge".

Because of this, forward edges can only occur in directed graphs.

---

Now, just in case you mixed up "forward edges" and "tree edges", the edge you describe still isn't necessarily a tree edge. It is only a tree edge if when crossing, that was the first time you've visited the destination node. The easy way to think about it in undirected graphs is that when you traverse an edge, it is a back edge if the destination node has been reached already, and a tree edge otherwise.