Question about spanning trees and creating them through BFS and/or DFS algorithms The question is as follows:
True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the root v.

What about if instead of DFS I used BFS?

I have no clue where to begin with this one. I feel like I'm overlooking some basic characteristic of the algorithm or the tree that it produces. Any help would be appreciated!
If you get to pick, each time, an ordering of the vertices, then statement is trivially true - just choose the ordering that gives that tree, but this is not interesting.

Assuming the vertices do have some fixed order (so the DFS/BFS can't arbitrarily pick which vertex it has to choose next), then statement is false. We can see this via a simple counting argument. As the ordering is fixed, the DFS/BFS produces a unique spanning tree for each starting vertex, i.e. we can produce at most $n$ spanning trees (per algorithm), where $n$ is the number of vertices in the graph.

However if our input graph is $K_{n}$ with $n &gt; 3$ (the complete graph on $n$ vertices), the graph has $n^{n-2}$ spanning trees, clearly far more than what we can produce from the DFS/BFS.