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

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