2
$\begingroup$

Suppose I have an undirected graph that consists only of a cycle. Each vertex has a depth value that must be $1$ greater than its predecessor (i.e. if we reach vertex $F$ from vertex $C$ which has a depth of $2$, then $F$ has a depth of $3$). The beginning vertex has a depth of $0$. I need to show that every vertex must have a depth $\le \lfloor \frac{n}{2} \rfloor$.

I know that because the graph is only a cycle, every vertex must have a degree of $2$. And when performing a breadth first search, each vertex (except for the beginning vertex) will only have one vertex to choose, as the other connected vertex would be its parent. This would create a kind of "tree" shape where every node except the root has one child, and would mean that the maximum depth is $\le \lfloor \frac{n}{2} \rfloor$. I'm not sure how to phrase this as a proof, though.

$\endgroup$
0
$\begingroup$

There may be other ways to prove your claim, the simplest seems to me is by induction on $n$.

Base case : $n=3$, that means input graph is a triangle and it is easy to see that in this case maximum depth is $\le \lfloor \frac{n}{2}\rfloor$

Inductive case: Suppose that depth of every vertex is $\le \lfloor \frac{k}{2}\rfloor$ in $k$ cycle graph want to prove that depth of every vertex is $\le \lfloor \frac{k+1}{2}\rfloor$ for $k+1$ cycle graph.

Hint for Inductive case: Going from $k$ cycle to $k+1$ cycle means we have added one vertex to any one of the edge ( as we know its both endpoints have depth $\le \lfloor \frac{k}{2}\rfloor$ (due to induction ) ) of the $k$ cycle graph it means depth of both endpoints in $k+1$ cycle will be $\le \lfloor \frac{k+1}{2}\rfloor$.

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