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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.