1

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.

Chris
  • 125
  • 2

1 Answers1

0

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