Proving that $\operatorname{rad}(G) \le \operatorname{diam}(G) \le 2\operatorname{rad}(G)$

graph theorysolution-verification

I am currently studying the textbook Graph Theory, fifth edition, by Reinhard Diestel. Chapter 1.3 Paths and cycles says the following:

A vertex is central in $G$ if its greatest distance from any other vertex is as small as possible. This distance is the radius of $G$, denoted by $\operatorname{rad}(G)$. Thus, formally, $\operatorname{rad}(G) = \min_{x \in V(G)} \max_{y \in V(G)} d_G(x, y)$. As one easily checks (exercise), we have
$$\operatorname{rad}(G) \le \operatorname{diam}(G) \le 2\operatorname{rad}(G)$$

The distance $d_G(x, y)$ in $G$ of two vertices $x$, $y$ is the length of a shortest $x$$y$ path in $G$. The greatest distance between any two vertices in $G$ is the diameter of $G$, denoted by $\operatorname{diam}(G)$.


My attempted proof is as follows:

We trivially know that $\operatorname{rad}(G) \le 2\operatorname{rad}(G)$ is true. So all that is left to prove is that $\operatorname{rad}(G) \le \operatorname{diam}(G)$ and $\operatorname{diam}(G) \le 2\operatorname{rad}(G)$.

We know that $\operatorname{rad}(G) \le \operatorname{diam}(G)$, since $\operatorname{diam}(G)$ is the greatest distance between any two vertices in $G$, so $\operatorname{rad}(G)$ cannot be greater than this. Formally,
$$\operatorname{rad}(G) = \min_{x \in V(G)} \max_{y \in V(G)} d_G(x, y) \le \max_{x \in V(G)} \max_{y \in V(G)} d_G(x, y) = \max_{x, y \in V(G)} d_G(x, y) = \operatorname{diam}(G)$$


But, as you can see, I'm not sure how to prove that $\operatorname{diam}(G) \le 2\operatorname{rad}(G)$. In particular, I can't figure out where the factor of $2$ in $2\operatorname{rad}(G)$ would come from. Thinking by analogy, in geometry, we know that the diameter of a circle is twice the radius, so this gives us a kind of handwavy clue as to why the factor of $2$ exists.

I would appreciate it if people would review the portion of the proof that I've completed on my own, and then help me understand how $\operatorname{diam}(G) \le 2\operatorname{rad}(G)$ is proved.

Best Answer

Let $y$ be a central vertex of $G$. Let $a, b$ be two vertices of $G$ such that $d_G(a,b) = diam(G)$. By triangular inequality: $diam(G) \le d_G(a, y) + d_G(y,b) \le rad(G) + rad(G) = 2 rad(G)$.

Your argument for $rad(G) \le diam(G)$ is valid to me. Doing the formal calcul is overkill.

Related Question