Directed graph is cyclic iff DFS gives back edges

Dependencies:

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

A directed graph contains a cycle iff DFS on that graph classifies some edges as back edges.

Proof

Suppose $G$ has a back edge $(v, u)$. Then $v$ is a descendant of $u$ in the DFS forest. Therefore, a cycle from $u$ to $v$ in $G$ can be obtained by going from $u$ to $v$ via tree edges and then going from $v$ to $u$ via $(v, u)$.

Suppose $G$ has a cycle $C$. Let $u$ be the first vertex in $C$ to be discovered. Since there is a path from $u$ to all other vertices in $C$ and those vertices are white when $u$ is discovered, all those vertices will become descendants of $u$ by the white path theorem.

Since $u$ is in a cycle $C$, there is at least one vertex $v$ in $C$ such that $(v, u)$ is in $G$. Since $v$ is a descendant of $u$, $(v, u)$ will be classified as a back edge.

Therefore, if $G$ is cyclic, it has a back edge.

Dependency for: None

Info:

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