# 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? – John Hughes Jun 6 '17 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) – Mohammed Farahmand Jun 6 '17 at 11:11
• For the second one, I was thinking of Kn, Cn, and Wn but none of them held this property. – Mohammed Farahmand Jun 6 '17 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? – John Hughes Jun 6 '17 at 11:53
• I guess by "same" it meant isomorphic. – Mohammed Farahmand Jun 6 '17 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.