2
$\begingroup$

I've been studying this topic, but there are a few questions I cannot find the answers to.

When must an edge of a connected simple graph be in every spanning tree for this graph?

For which graphs do depth-first search and breadth-first search produce identical spanning trees no matter which vertex is selected as the root of the tree?

$\endgroup$
  • 1
    $\begingroup$ What are your thoughts? Have you drawn out 10 or 12 examples? $\endgroup$ – John Hughes Jun 6 '17 at 11:08
  • $\begingroup$ Well, the spanning tree will definitely include an edge which is necessary for the graph to be connected. Because if any edge which is needed for the graph to be connected is removed, it won't be a tree anymore (by the definition of tree) $\endgroup$ – Mohammed Farahmand Jun 6 '17 at 11:11
  • $\begingroup$ For the second one, I was thinking of Kn, Cn, and Wn but none of them held this property. $\endgroup$ – Mohammed Farahmand Jun 6 '17 at 11:12
  • $\begingroup$ One question is "what does it mean to have just one spanning tree or for two spanning trees to be "the same"?" Think of a triangle ABC. The tree A - B - C (where $A$ is the root, $B$ is its child, and $C$ is $B$'s child) and the tree in which $B$ is the root and $A$ and $C$ are both its children) are both spanning trees. The first has depth 2; the second has depth 1. But they contain exactly the same edges of the original graph. Are these "the same tree" or different trees? $\endgroup$ – John Hughes Jun 6 '17 at 11:53
  • $\begingroup$ I guess by "same" it meant isomorphic. $\endgroup$ – Mohammed Farahmand Jun 6 '17 at 12:45
3
$\begingroup$

Your comment that an edge which is necessary for the graph to be connected must be in every spanning tree is correct. In fact this is the only reason an edge can be in every spanning tree: if the edge isn't necessary for the graph to be connected we can remove it, and the remaining graph is still connected so it still has a spanning tree.

For the second one, one way it can be true is if there is only one spanning tree. What graphs have a unique spanning tree?

Suppose $xy$ is an edge which is not in every spanning tree. Try to show that (for some ordering of the vertices) BFS uses the edge $xy$ and DFS doesn't.

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