Graph height, diameter and radius relation 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$
 A: Since the diameter $D$ is the longest shortest path in the whole graph and $H$ is the height, which is the longest shortest path from a dedicated vertex $r$, the root (sometimes called the center), to any other vertex in $G$, $H$ can be at most $D$. Now, consider a path between two vertices $u$ and $v$ with length $D$. Let $x$ be a third vertex and two paths between $u$ and $x$ and $v$ and $x$ with each of them having a length of at most $H$. Then the path $u - x - v$ has length at most $2H$. It follows that $D \leq 2H \iff \frac{D}{2} \leq H$.
A: 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$.
