2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Please don't edit the content out of your question. If you've found the answer, you'll be able to write it up as an answer 8 hours after posting the question. $\endgroup$ – Gilles Mar 26 '14 at 23:48
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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