Is there any connected-graph example other than the complete graph where Diameter(G) = Radius(G)

Question

We know that, for any graph G, Radius(G) ≤ Diameter(G) ⩽ 2*Radius(G). I was wondering whether there is any connected graph other than the complete graph, where Radius(G) = Diameter(G).

Answer 1

You're looking for graphs in which every vertex has the same eccentricity. So, in particular, any vertex-transitive graph (which, informally, "looks the same" from any vertex) would do: one simple example, aside from complete graphs, is the cycle graph $C_n$, for any number of vertices $n \ge 3$.

To find many more examples, you can use the search feature of the House of Graphs. It doesn't let you directly find graphs with the same diameter and radius but you can, for example, list graphs with radius 2 and diameter 2 (or any other fixed value). One of the smallest non-vertex-transitive graphs I found there in this way is the house graph, and here is a nice example with radius and diameter both $4$. Both are also shown below:

---

Actually, there's a sense in which almost all graphs have equal diameter and radius. If you pick an $n$-vertex graph by flipping a coin for each of the $\binom n2$ possible edges to see if it's present, then:

• It's very unlikely for a vertex $v$ to have eccentricity $1$ (you'd need all $n-1$ edges out of $v$ to be present, which happens with probability $\frac1{2^{n-1}}$). So the overall probability of having any such vertex is at most $\frac{n}{2^{n-1}}$, which is tiny.
• It's also very unlikely that there's no path of length $2$ between two vertices $v,w$: there are $n-2$ possible paths, each of which is present with probability $\frac14$, so the probability is $(\frac34)^{n-2}$. So the overall probability of having any such pair is at most $\binom n2 (\frac34)^{n-2}$, which is also tiny.

Therefore it's overwhelmingly likely, for large $n$, that a graph chosen in this way has both radius and diameter $2$.