Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 3

Problem:

This problem explores the relationship between two definitions about graph distances. In this problem, we consider only graphs that are undirected and connected. The diameter of a graph is the maximum, over all choices of vertices $s$ and $t$, of the shortest-path distance between $s$ and $t$. (Recall the shortest-path distance between $s$ and $t$ is the fewest number of edges in an $s-t$ path.)
Next, for a vertex $s$, let $l(s)$ denote the maximum, over all vertices $t$, of the shortest-path distance between $s$ and $t$. The radius of a graph is the minimum of $l(s)$ over all choices of the vertex $s$.
Which of the following inequalities always hold (i.e., in every undirected connected graph) for the radius $r$ and the diameter $d$? [Select all that apply.]

Solution

$r \le d$ is obvious, $d$ is maximum of all shortest paths and $r$ is the minimum all longest shortest path with a fixed source.

What is not so obvious is $r \ge \frac{d}{2}$. Suppose that is not true, then let $S-T$ be the diameter path (i.e. the longest shortest path) and $c$ (for center) stand for the $s$ we chosen for $r$.

Now $c - S$ path is of length at most $r$, and so is the $c - T$ path, therefore the path $S - c - T$ has length at most $2r$, and we know that this must be at least $d$, therefore, we have $r \ge \frac{d}{2}$.