# What are possible uses for cross, back and forward edges after the DFS visit?

The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles.

What are other useful algorithms that use these labels?

Think of the following problem: Given a directed graph $$G = (V,E)$$, determine whether there is a pair of vertices $$u, v$$, s.t $$u\neq v$$ and $$\mathit{and}$$ there are at least two $$\mathbf{simple}$$ paths from $$u$$ to $$v$$.

Hint: use the edge labels given by the $$DFS$$.

Solution:

If and only if there are any "cross" or "forward" arcs in the tree given by a $$DFS$$ tour on $$G$$, then a pair of vertices $$u, v$$ exists s.t are at least two $$\mathbf{simple}$$ paths from $$u$$ to $$v$$.

Proof:

1. Suppose no "Cross" or "Forward" Arcs exist. Then the tree given by the $$DFS$$ is a directed tree, with some "Backwards" arcs. A tree by definition has only one path between every pair of vertices, and below it is shown backwards arcs only add new simple paths.

Consider the backward arc $$(u,v)$$:
$$\bullet$$ for all the ancestors of $$v$$, it only adds non simple paths.
$$\bullet$$ for all the descendants of $$v$$ and ancestors of $$u$$, denoted by $$w$$ (vertices between $$u$$ and $$v$$ on the tree), it adds one simple path from $$w$$ to any vertex below (including) $$v$$ and above (excluding) $$w$$. All these paths are new because the tree is directed, and all other paths are non-simple, because they contain a cycle.
$$\bullet$$ for descendants of $$u$$, it makes no difference.

2.
$$\bullet$$ Suppose a "Cross" arc exists between $$(u,v)$$. Then $$u$$ cannot be the root of the tree (the proof is trivial and omitted). Which means the following simple paths exist: $$r \rightarrow v$$, $$r \rightarrow u$$, $$r \rightarrow u \rightarrow v$$
$$\bullet$$ Suppose a "Forward" arc exists between $$(u,v)$$. Then $$v$$ is a descendant of $$u$$, but not a child of $$u$$, therefore there are at least two simple paths from $$u$$ to $$v$$.