tree, back, forward and cross edges

Run a depth-first search and every edge of the graph ends up playing one of just four roles relative to the DFS tree. Think of the tree as the family lineage the search built — parents discovering children, those children discovering grandchildren. Each remaining edge either reaches back up the family line, down it, or sideways to a different branch. These four roles — tree, back, forward, cross — are the complete vocabulary for talking about how a graph's edges sit against the search that explored it.

Here are the four, with the structural fact each one signals. A tree edge u->v is one DFS used to first discover v; the tree edges alone form the DFS tree. A back edge goes from a vertex u down in the tree up to one of u's ancestors v (its interval still open, v still on the recursion stack) — and a back edge is the exact certificate that a cycle exists, since the tree path from v down to u plus the back edge u->v closes a loop. A forward edge goes from an ancestor u to a proper descendant v that was already finished, having been discovered earlier by a longer tree route — it is a shortcut down the tree. A cross edge connects two vertices in different branches (or different DFS trees) where neither is an ancestor of the other; in the timestamp picture, u finds v already finished with disjoint intervals. A clean rule of thumb: in undirected graphs only tree and back edges occur; forward and cross edges need direction.

Why keep these straight? Because the entire toolkit of this field is phrased in them. Cycle detection is 'does any back edge exist?'. A directed acyclic graph is precisely a directed graph with no back edges under DFS, which is why topological sort works. Strongly-connected-component algorithms and articulation-point detection both hinge on comparing a vertex against the lowest ancestor reachable through back edges. The honest subtlety: which edges are forward versus cross can flip if you restart DFS from a different vertex or scan neighbours in another order — those labels are run-relative. The one label that is graph-intrinsic is the existence of a back edge, because it corresponds to a genuine cycle no matter how the search was steered.