Define the diameter of a graph G—denoted diam G—to be the length of a longest path in G between two different vertices. For a given vertex v, there is a maximum length of of the non-closed paths with initial vertex v, and we define the radius of G to be the smallest of these maximum lengths. More compactly:
Gerstein, Larry J.. Introduction to Mathematical Structures and Proofs (Undergraduate Texts in Mathematics) (p. 275). Springer New York. Kindle Edition.
$rad (G) = min_{v\in V}(max_{w\in V}\{d(v,w)\})$
where d(v,w) is the length of the shortest path between vertices v and w
The problem is to prove $diam(G) \le 2 rad(G)$
I seem to have a counter-example: a graph that is a triangle ABE with an edge BC hanging off of it:
According to my calculations, for vertex B, $max\{d(B,w)\}=1$, so the "radius" is one. But the diameter is the length of the path CBAE, which is three. So $d \nleq 2r$
Why am I wrong, or it is possible that I am right?
Best Answer
As you write $$ rad(G) = \min_{v\in V} \max_{w\in V} d(v,w)$$ and $$ diam(G) = \max_{v\in V} \max_{w\in V} d(v,w).$$
Suppose that the diameter is realized by $v',w'$, then $diam(G) = d(v', w')$. Also assume that $rad(G)$ is realized at $v''$, that is, $rad(G) = \max_{w\in V} d(v'',w)$.
By triangle inequality:
$$ d(v',w') \le d(v',v'') + d(v'', w') \le 2\max_{w\in V} d(v'',w) = 2rad(G).$$