First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS
What I tried was to do both DFS and BFS on a couple of graphs and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ.


Indeed, the spanning trees formed by the first-visited nodes might be different from DFS and BFS. For example, try a cycle graph of four vertices. When the spanning tree are different, the number of edges is still the same for both.

You might have noticed that the number of edges is always one less than the number of vertices of the graph, either by concentration or by luck, had you been playing with connected graphs long enough.

In fact, the number of edges in every spanning tree of a connected graph is always one less than the number of vertices in that graph. This comes from the following two facts.


The number of edges in a tree is one less than the number of vertice of that tree.
The vertices in a spanning tree of a connected graph are the vertices of that graph.


Exercise. What about disconnected graphs?