Relative to the resulting DFS edge classification, a tree edge in depth-first search discovers a white vertex and becomes its parent edge. A forward edge in depth-first search goes to a proper descendant but is not that descendant's discovery edge. A back edge in depth-first search goes to an active ancestor, with a self-loop also counted as a back edge when such edges are allowed. A cross edge in depth-first search joins vertices with no ancestor-descendant relationship in the forest, such as different completed branches or different trees.
The definitions refer to directed edges; an undirected graph is normally classified only with tree and back edges, accounting for the reverse copy of a parent edge separately.
True for a directed cycle. Suppose there were no back edges. On examining an edge , its target would either be white, in which case its recursive call finishes before ; 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 .
Applying those strict inequalities around a directed cycle would imply , 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.