1
$\begingroup$

Possible Duplicate:
Proof related to breadth first search

I'm trying to prove the following:

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{n/2}\rfloor}$ levels apart.

Not sure how to approach this, tried googling properties of BFST's and cycles, but no avail, any help or resources would be helpful!

2 Answers 2