= Solution
\b[True for a directed cycle.] Suppose there were no back edges. On examining an edge $u\to v$, its target would either be white, in which case its recursive call finishes before $u$; or black, in which case it has already finished. A gray target would be an active ancestor and hence give a back edge, contrary to the supposition. Therefore every edge would satisfy $f(v)<f(u)$.
Applying those strict inequalities around a directed cycle would imply $f(u)<f(u)$, a contradiction. Thus some <back edge in depth-first search> must exist in the search's edge classification. Such an edge is classified relative to the DFS forest; it is not one of the forest's tree edges.
Back to article page
