Diameter and Radius and Well Known Inequality, Which one is preferable?

Question

An un-directed graph $G$ is given.

The diameter of a graph is the maximum of shortest paths between two vertices of the graph.

$L(S)$ is maximum length of shortest paths from $S$ to other vertices.

The radius of a graph is minimum value of $L(S)$ among all vertices.

If $d$ and $r$ be diameter and radius of graph two following inequalities always hold:

$A)$ $r \leq d$

$B)$ $r \geq \frac{d}{2}$

But my note tells me that $B$ is better than of $A$ (maybe by 'better' word, it means that it always holds or any condition that be logical... I don't know for example one of them works with negative weights or anything else in Graph)

I see both of them in all of graph books but anyone can distinguish between these two case, is there any difference here that we can prefer $B$ to $A$?

Answer 1

Let me begin by saying that your question almost makes no sense. As @MorganRodgers very explicitly said, when comparing bounds, you need $2$ lower ones or $2$ higher ones, to find which one is better.

A an example, here are $2$ upper bounds for $n!$

$$n!<n^n\text{ and } n!<\bigg(\frac{n+1}{2}\bigg)^n$$

The first one comes from the fact that $1,2,...,n-1<n$ and the second one comes from the $Am-Gm$ inequality. You can clearly tell that the second higher bound is better (or tighter), because it is smaller.

You cannot prefer a lower bound over a higher bound or viceversa. They do different things It's like saying you prefer to draw with a spoon over eating soup with a pencil.

However, I think what you want to prove is the fact that $d-r>r-\frac{d}{2}$, in other words, the lower bound is closer to the actual value than the higher bound.

---

Lets begin by clarifying the notions. Consider a graph $G$ and let the set of the vertices of $G$ be $V(G)$.

For any pair of vertices $v,u\in V(G)$, the distance between $u$ and $v$ is denoted with $d(u,v)$ and is equal to the length of the shortest path that connects $u$ and $v$. If $u$ and $v$ are not connected this is equal to $\infty$ and if $u=v$ then the distance is $0$

For any $v\in V(G)$, the eccentricity of $v$ is denoted by $\varepsilon(v)$ and satisfies the following relation $$\varepsilon(v)=\max_{u\in V(G),u\neq v}d(u,v)$$

The radius of a graph $G$ is $$r=\min_{v\in V(G)}\varepsilon(v)$$

The diameter of a graph $G$ is $$d=\max_{v\in V(G)}\varepsilon(v)$$

Using what we have just found out, we can see that sometimes the higher bound is closer to $r$ than the lower bound and sometimes the lower bound is closer to $r$ than the higher bound.

For example take a complete graph $K_n$. In this case, $d=r=1$ so $d-r=0<\frac{1}{2}=r-\frac{d}{2}$ so in this case we could say that the higher bound is "better".

But when we take a complete bipartition $K_{n,n}$, $d=2$ and $r=1$ so in this case $d-r=1>0=r-\frac{d}{2}$

---

So to conclude the answer, sometimes the $\frac{d}{2}$ is closer to $r$ and sometimes $d$ is closer to $r$. You cannot prefer a bound over another.