DFS: Edge classification in undirected graphs

Dependencies:

1. DFS: Edge classification
2. DFS: White-path theorem

When DFS is performed on an undirected graph $G$, all edges are either tree edges or back edges.

Proof

Without loss of generality, assume visit(u) is called before visit(v). Therefore, $v$ was white when visit(u) was called. By the white path theorem $v$ will be a descendant of $u$ in $G_π$. Therefore, in the directed version of $G$, $(v, u)$ is a back edge and $(u, v)$ is either a tree edge or a forward edge.

By using precedence rules, we get that in the undirected graph $G$, $(u, v)$ is either a tree edge or a back edge.

Dependency for:

1. Undirected graph is cyclic iff DFS gives back edges

Info:

• Depth: 6
• Number of transitive dependencies: 12

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Transpose of a graph
6. Path in Graph
7. Rooted tree
8. Forest
9. Properties of DFS
10. DFS: Edge classification
11. DFS: Parenthesis theorem
12. DFS: White-path theorem