Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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...
