1
$\begingroup$

Suppose a connected graph G has a cycle C of length n. Prove that in any breadth-first search tree of G, any two vertices in C are at most $\lfloor\frac{n}{2}\rfloor$ levels apart.

No idea how to work this one. some hints on where to start will be appreciated!

1 Answers 1

1

The level of a vertex in such a tree is the number edges in a shortest path to the root. Any two vertices in $C$ are at most $\lfloor \tfrac{n}{2} \rfloor$ edges apart. So traveling from one vertex in $C$ via another one in $C$ to the root...