# Spanning Tree of a Simple Graph

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?

• What are your thoughts? Have you drawn out 10 or 12 examples? Commented Jun 6, 2017 at 11:08
• 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) Commented Jun 6, 2017 at 11:11
• For the second one, I was thinking of Kn, Cn, and Wn but none of them held this property. Commented Jun 6, 2017 at 11:12
• 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? Commented Jun 6, 2017 at 11:53
• I guess by "same" it meant isomorphic. Commented Jun 6, 2017 at 12:45

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.