Question

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? Justify your answer.

Short answer

The connected simple graph has a tree.

Step-by-step solution

Definition

An undirected graph within which there’s at the most one edge between each pair of vertices, and there are not any loops, which is a grip from a vertex to itself.

Graph has one spanning tree.

For this result consider the contrary. Let G is a simple connected graph that is not a tree and has some spanning tree T using both breadth-first and depth-first search. As G is not a tree, there must be a cycle in G. If breadth-first is used the loss of generality assumed is the first in the cycle C to be encountered, then will be children of for all. On the other hand, if used depth-first, all the vertices in C will appear on a single path, thus proving by contradiction.

Therefore, the connected simple graph has a tree.