Understanding the "ordering of the four types of edges" in DFS
I have reviewed section 22.3, &quot;Depth-first search&quot; a couple of times.

&quot;What does it mean by &quot;the ordering of the four types in the classification scheme&quot;? In particular, what does the &quot;ordering&quot; 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$.

$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).

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)$.

$u.d = 1$
$x.\pi = u$
$x.d = 2$
$v.\pi = x $
$v.d = 3$
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.
$v.f = 4$
$x.f = 5$
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.
$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.