Graph height, diameter and radius relation

graph theoryinequality

I have a BFS tree with height H, diameter D. I have to show that $\frac{d}{2} \leq H \leq D $.

This is what I have done:

Assume H > D. Then the number of nodes from leaf to root ( Height ) is greater than the number of nodes in longest path ( Diameter) which is a contradiction. Hence, $H \ngtr D $.
Next, H can be equal to D because the longest path can be H itself, therefor H=D. Lastly,Assume $H \nless D$ but i can show a counter example and contradict this claim.

Therefore, in conlucion, $H \leq D$. (is this correct ?)

How do I show that former part, $D/2 \leq H$

Best Answer

The first part is correct : since the height $H$ is the distance between the root and the furthest leaf and the diameter $D$ is the largest distance between points of the graph, we have $H\leq D$.

For the second part : Let $x_1,x_2$ be any two vertices in the graph. There is a path of lenght $\leq H$ joining $x_1$ to the root and one joining $x_2$ to the root. By concatenating both, we obtained a path of length $\leq 2H$ connecting $x_1$ and $x_2$. Hence, $D\leq 2H$.