Let G be a connected graph with the property that both BFS and DFS starting from some node v return the same tree. Complete the proof below to argue that G itself must be a tree. In the proof, use only these facts:

1. Let T be a breadth-first search tree, let x and y be nodes in T belonging to layers L_i and L_j respectively, and let (x, y) be an edge of G. Then i and j differ by at most 1.

2. Let T be a depth-first search tree, let x and y be nodes in T, and let (x, y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.

Proof: Let T be the tree returned by both BFS and DFS. We will show that G is equal to T. Suppose for the sake of contradiction that G has a non-tree edge, that is, an edge (x; y) that does not belong to T.