Each directed graph Has 0 crossing edges in Some DFS Run?

44 Views Asked by At

I found the following claim online:

For each directed graph, There is DFS run such that it contains 0 crossing edges.

Why is this correct at all?

I think I found a counter example, consider a graph with 3 vertices 1,2,3 with the following directed edges:

1->2, 1->3, 2->3