Understanding the "ordering of the four types of edges" in DFS

Question

The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).

Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge according to whether $(u,v)$ or $(v,u)$ is encountered first during the depth-first search is equivalent to classifying it according to the ordering of the four types in the classification scheme.

Problem: What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to? What is supposed to prove?

---

The classification scheme is defined on page 609:

We can define four edge types in terms of the depth-first forest $G_{\pi}$ produced by a depth-first search on $G$:

1. Tree edges are edges in the depth-first forest $G_{\pi}$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.
2. Back edges are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree.
3. Forward edges are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
4. Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

---

Added Example:

Consider the figure below.

Suppose that a DFS starts from node $u$ and travels along $(u,x)$ first and then $(x,v)$. Both $(u,x)$ and $(x,v)$ are tree edges.

What about the edge $(v, u)$? It should be a back edge according to the classification scheme in the textbook. How is $(v,u)$ classified as back edge according to the classification in the exercise?

Is $(v,u)$ a tree edge while $(u,v)$ a back edge according to the definition in the exercise? This is strange, because in an undirected graph, $(u,v)$ and $(v,u)$ refer to the same edge.

Answer 1

I have reviewed section 22.3, "Depth-first search" a couple of times.

"What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to?

While quoting the textbook, You have used 1, 2, 3 and 4 to label the four cases in the classification scheme. That is an ordering. All it means is that $1 \prec 2 \prec 3 \prec 4$. In other words, tree edges precede back edges, which precede forward edges, which precede cross edges.

---

What is supposed to prove?

Suppose we have done a depth-first search $S$ on an undirected graph $G$ that has produced the depth-first forest $G_\pi$ as describe in the textbook.

An edge $e=\{u,v\}=\{v,u\}$ can be represented by either the directed edge $(u,v)$ or the directed edge $(v,u)$. Note that $(u,v)\not=(v,u)$. Both $(u,v)$ and $(v,u)$ will be explored during $S$. There are two methods to classify $e$ with respect to $S$.

1. $e$ is classified as the earliest type of edge (according to that ordering) which either $(u,v)$ or $(v,u)$ can be classified as.
   More specifically, if either $(u,v)$ or $(v,u)$ is classified as a tree edge, then $e$ is classified as a tree edge. Otherwise, $e$ is classified as a back edge. Note that at least one of $(u,v)$ and $(v,u)$ must be classified as either tree edge or back edge (theorem 22.10 of the book).

2. If $(u,v)$ is discovered earlier than $(v,u)$, then $e$ is the same type of edge as $(u,v)$. If $(v,u)$ is discovered earlier than $(u,v)$, then $e$ is the same type of edge as $(v,u)$.

That exercise asks readers to prove the above two classifying methods are equivalent. That is, $e$ is classified as type $X$ by the first method if and only if $e$ is classified as type $X$ by the second method, given any edge $e$ and any type $X$.

(Somewhat informally, an edge is a tree edge if it appears in the resulting tree; otherwise it is a back edge. This seems to be the simplest way to label edges in an undirected graph with respect to a DFS.)

---

Let us take a look at the example given in the question.

Here is the relevant part of running DFS-VISIT $(G,u)$.

1. $u.d = 1$
2. $x.\pi = u$
3. $x.d = 2$
4. $v.\pi = x $
5. $v.d = 3$
6. Now we discover edge $(v,u)$, which connects $v$ to $u$, which is an ancestor of $v$ since $v.\pi=x$ and $x.\pi = u$. That is, $(v,u)$ is a back edge. This is the first time edge $e$ is discovered. So $e$ is a back edge according to second classifying method.
7. $v.f = 4$
8. $x.f = 5$
9. Now we discover edge $(u,v)$, which connects $u$ to its descendant $v$. This edge $(u,v)$ is classified as a forward edge. Since $(v,u)$ is classified as a back edge, a type of edges that precedes a forward edge, $e$ is a back edge according to the first classifying method.
10. $u.f = 6$

We just saw that $e$ is classified as the same type of edge according to either classifying method. That exercise asks readers to prove that is not a coincidence.