Breadth first search tree's cycles

Question

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!

Answer 1

HINT: Let $v_1$ be the first vertex in $C$ that you hit in your search. Its two neighbors in $C$ will be among its children in the search tree. Their neighbors other than $v$ will be one level deeper in the search tree, and so on. For each $v\in C$ let $d(v)$ be the distance from $v_1$ to $v$ in $C$ (i.e., the length of the shorter of the two routes from $v_1$ to $v$ in $C$). Can you see that $v_1$ and $v$ are at most $d(v)$ levels apart? (The actual proof of this will be a finite induction.) What’s the maximum possible value of $d(v)$ for $v\in C$?

Answer 2

Let $C=v_1v_2\dots v_nv_1$ be the cycle. Let $v_1$ be the first vertex added into the BFS tree. Since vertices are added to any BFS tree in non-decreasing order, then $v_1$'s two neighbours in $C$ will either be in the same level as $v_1$, or one level apart (they will be one level apart at most because there is a non-tree edge joining $v_1$ to its two neighbours, and non-tree edges join vertices at most 1 level apart). The same is true for the rest of the vertices in $C$ - adjacent vertices are at most 1 level apart.

The shortest path between $v_1$ and any other vertex in C is $|n/2|$. This means $v_1$ is at most $|n/2|$ levels away from any $v$ in $C$ as well, since $v_1$ is connected to $v$ by $|n/2|$ edges, represented by $|n/2|$ edges in the BFS tree that can be at most 1 level apart. Since the furthest vertex is at most $|n/2|$ levels away from v1, then all vertices in $C$ are at most $|n/2|$ levels away from $v_1$ (i.e. $\operatorname{level}(v) \leq \operatorname{level}(v_1) + |n/2|$ for all $v\in C$), and since $v_1$ was the first vertex added, then $\operatorname{level}(v) \geq \operatorname{level}(v_1)$ for all $v\in C$.

$\operatorname{level}(v_1) \leq \operatorname{level}(v) \leq \operatorname{level}(v_1) + |n/2|$ for all $v\in C$, so all vertices are within $|n/2|$ levels of each other.