$$We have a connected graph G $=($V$,$E$),$ and a specific vertex u $$ V$.$ Suppose we compute a depth$-$first search tree rooted at u$,$ and obtain a tree T that includes all nodes of G$.$ Suppose we then compute a breadth$-$first search tree rooted at u$,$ and obtain the same tree T$.$ Prove that G $=$ T$.($In other words, if T is both a depth$-$first search tree and a breadth$-$first search tree rooted at u$,$ then G cannot contain any edges that do not belong to T$.)$

Excerpt From

Algorithm Design

TARDOS

This material may be protected by copyright.