A graph can have multiple spanning trees and the spanning tree resulting from a depth-first search depends on the order in which edges are processed. Can every possible spanning tree of a given graph be produced from that graph if the edge processing order is determined appropriately?


1 Answer 1


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 is.

  • $\begingroup$ Another easy example can be a cycle $C_n$. $\endgroup$
    – codeR
    Commented Apr 9 at 11:05
  • $\begingroup$ @codeR all spanning trees of a cycle $C_n$ can be obtained using DFS if you can choose edge ordering AND starting vertex. $\endgroup$
    – Nathaniel
    Commented Apr 9 at 13:19
  • $\begingroup$ Yes, indeed, if you change the start vertex. But the question only asks about selecting edges in different order once you start. $\endgroup$
    – codeR
    Commented Apr 9 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.