# For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross trees

I suspect that it is not true but I came across with the following statement:

For any direct graph $$G(V,E)$$, there is always an iteration of DFS algorithm on $$G$$ so the result does not have any cross edges.

Is it possible to show an example to disprove it?

• What's a cross tree? Also what's an iteration of the DFS algorithm? Jul 22 at 20:16
• @Steven Sorry I meant "cross edge". By "iteration of DFS" I mean, starting from different vertex. Jul 23 at 10:39
• Is there any particular order in which the edges of the currently visited vertex need to be examined during the DFS? Jul 23 at 10:51

A possible DFS starting from $$a$$ visits the vertices in this order: $$\langle a, b, c, d \rangle$$ producing the cross-edge $$(c,b)$$.
A possible DFS starting from $$b$$ visits the vertices in this order: $$\langle b, a, c, d \rangle$$ producing the cross-edge $$(d,c)$$.
A possible DFS starting from $$c$$ visits the vertices in this order: $$\langle c, a, b, d \rangle$$ producing the cross-edge $$(d,b)$$.
A possible DFS starting from $$d$$ visits the vertices in this order: $$\langle d, a, b, c \rangle$$ producing the cross-edge $$(c,b)$$.
• Sure. Just split $(b,a)$, $(c,a)$, and $(d,a)$ by adding a middle vertex. Argue similarly to what I did in the answer to handle depth first searches starting from the newly added vertices. Jul 23 at 14:17