DFS Edge Classification

Four Edge Types

During DFS on a directed graph, every edge $(u, v)$ is classified based on the colour of the target vertex $v$ at the moment the edge is first explored from $u$. There are four classifications:

1. Tree edge: $v$ is WHITE. The edge is added to the DFS forest; $v$ becomes a child of $u$ in the depth-first tree. Discovered during: DFS-VISIT(u) → v.colour == WHITE → call DFS-VISIT(v).
2. Back edge: $v$ is GREY. $v$ is an ancestor of $u$ in the current DFS tree. Indicates a directed cycle exists. Example: $u \to \text{ancestor}(u)$.
3. Forward edge: $v$ is BLACK and is a descendant of $u$ in the DFS forest (but not a direct child; direct children are tree edges). Connects a vertex to a non-child descendant.
4. Cross edge: $v$ is BLACK and is neither an ancestor nor a descendant of $u$. Either connects different subtrees of the same DFS tree, or connects vertices in different DFS trees entirely.

The classification depends on DFS exploration order: the same edge might be classified differently if adjacency lists are processed in a different order.

Timestamp-Based Characterisation

The timestamps give precise, colour-independent criteria. For edge $(u, v)$:

• Tree or forward edge iff $d[u] < d[v] < f[v] < f[u]$. The target’s interval is nested inside the source’s. To distinguish tree from forward: for tree edges, $v$ was discovered via this specific edge; for forward edges, $v$ was discovered through a different path but is still a descendant.
• Back edge iff $d[v] \le d[u] < f[u] \le f[v]$. The target was discovered before the source and finishes after the source. This is the hallmark of cycles.
• Cross edge iff $d[v] < f[v] < d[u] < f[u]$. The entire interval of $v$ lies before the entire interval of $u$.

Properties Through an Example Walk

Run DFS on this directed graph: $1 \to 2$, $1 \to 3$, $2 \to 3$, $2 \to 4$, $3 \to 5$, $4 \to 5$, $5 \to 6$, $6 \to 7$, $7 \to 6$, $5 \to 8$, $8 \to 4$.

Discovery and finish times (assuming adjacency lists in numerical order, starting from 1):

Vertex	1	2	3	4	5	6	7	8
$d$	1	2	3	4	5	6	8	9
$f$	16	15	10	7	12	11	14	13

Classify each edge:

• $(1,2)$: tree (2 white). $(1,3)$: forward (3 black, descendant: $d[1] < d[3] < f[3] < f[1]$, but 3 discovered via 2, not 1).
• $(2,3)$: tree. $(2,4)$: tree.
• $(3,5)$: tree.
• $(4,5)$: forward (5 discovered later via 3, but is descendant of 4).
• $(5,6)$: tree. $(5,8)$: tree.
• $(6,7)$: tree.
• $(7,6)$: back (6 is grey when exploring $7 \to 6$; also $d[6]=6 \le d[7]=8$, $f[6]$ is not assigned yet but $f[7] < f[6]$ — back edge).
• $(8,4)$: back (4 is grey when exploring $8 \to 4$; or by timestamps: $d[4]=4 \le d[8]=9$ and $f[8]$ is not yet assigned before $8$ finishes, but $f[4]=7 < f[8]=13$ — confirms ancestor relationship).

The presence of back edges $(7,6)$ and $(8,4)$ confirms cycles in the graph.

Undirected Graphs

In an undirected graph, DFS processes each edge in both directions (once from each endpoint). This restricts the possible classifications:

• Tree edges occur when the neighbour is white.
• Back edges occur when the neighbour is already discovered but is not the immediate parent (the vertex from which we just arrived). The edge $(v, \text{parent})$ explored in reverse is trivially a back edge under the directed definition; in the undirected context, we treat this as the reverse of the tree edge and not a cycle-indicating back edge.

Forward and cross edges cannot occur in undirected graphs. Proof: if $(u,v)$ were a forward edge (descendant), then exploring from $v$ would encounter $u$ as a back edge; but the symmetric relationship means the edge would already be part of the DFS tree. Cross edges would imply exploring from $u$ first then from $v$ later, but if $(u,v) \in E$, the second exploration would encounter the other vertex immediately, making it a back edge.

Conclusion for undirected graphs: Every edge is either a tree edge or a back edge. A back edge (to a non-parent ancestor) indicates an undirected cycle.

Cycle Detection

• Directed graph is a DAG iff DFS produces no back edges. Algorithm: run DFS; if any edge $(u, v)$ is explored with $v$ coloured GREY, report “contains cycle”. Time: $\Theta(|V| + |E|)$.
• Undirected graph has a cycle iff any non-tree back edge exists.

This is a fundamental result: DFS provides linear-time cycle detection for both directed and undirected graphs.

Summary

Edge Type	Target Colour	Timestamp Condition	Significance
Tree	WHITE	$d[u] < d[v] < f[v] < f[u]$	Part of DFS forest
Back	GREY	$d[v] \le d[u] < f[u] \le f[v]$	Indicates cycle
Forward	BLACK, descendant	$d[u] < d[v] < f[v] < f[u]$	Non-tree shortcut to descendant
Cross	BLACK, unrelated	$d[v] < f[v] < d[u] < f[u]$	Between subtrees or trees

Graph type	Allowed edge types
Directed	All four types
Undirected	Tree + Back only

Application	Detail
Cycle detection in directed graphs	Back edge $\iff$ cycle, $\Theta(V+E)$
Acyclicity test	No back edges in DFS

Past paper questions: y2026p1q10 (DAG and topological sort via DFS).