Let G = (V, E) be a connected graph. Suppose a depth-first search from a specific node

u € V produces a tree T that includes all nodes of G. Additionally, let a breadth-first search from the same

node u result in the same tree T. Prove that G cannot contain any edges that do not belong to T.

Hint: proof by contradiction.