Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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 > 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.
