Consider a complete graph $K_n$. Then a depth-first search can only create a linear-path spanning tree, no matter what the edges processing order.
Nathaniel
- 17k
- 2
- 30
- 55