First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS

Question

I am trying to state, whether the statement is true:
During a DFS/BFS, first time visited nodes form a spanning tree, that has the same number of edges whether you use DFS or BFS.
Is it true? Thanks!

Answer 1

Yes, DFS and BFS generate trees with the same number of edges. DFS and BFS create trees with different shapes. But in both cases, each vertex is connected by an edge with its neighboring vertex. There is no circle in the tree. Then the number of edges should be the same for DFS and BFS.