I've been trying to see if this statement is true or false for unweighted connected graphs.
$$
\frac{\operatorname{diam}G}{\operatorname{apd}G}\leq c, \quad c\in\mathbb{R^+}
$$ where $\operatorname{diam}G$ is the maximum distance possible between two vertices in a graph, and $\operatorname{apd}G$ is the average pairwise distance between 2 vertices and is $\frac{\sum{\operatorname{dist}(u,v)}}{\binom{\text{number of vertices}}{2}}$. I've tried drawing out graphs (from 3 to 6 vertices) from the minimum connected graph of a simple path to the complete graph. The complete graph always yields $\frac{1}{2}$ while the the simple path has the largest value that always increases, so I tried to find the simple path value for increasing vertices. I denote the ratio for the simple path to be $R_v$ where $v$ is the number of vertices in the graph, and I get:$$
R_2=\frac{1}{2},R_3=\frac{3}{4}, R_4=\frac{9}{10},R_5=1,R_6=\frac{15}{14}, R_7=\frac{9}{8},R_8=\frac{7}{6},R_9=\frac{6}{5}
$$ It seems to me that it is an increasing sequence, but I cannot seem to see any sort of pattern in it. It looks like the terms are a subset of the sequence $\{\frac{n+1}{n}\}$ and that as $v\to\infty$, $n\to0$, so the terms look like they go to some arbitrarily large value when v gets bigger and bigger, so the statement might be false. But of course I can't prove it. They might decrease the rate of increase to the point where there is an upper-bound. I have also searched online for what other people might have said on this, and some sources (other university solutions) said that the statement is false. They said to draw a star-shaped wand, but I have no idea what that is. Ideally, there'd be a graph where the $R_v$ is a sequence that can be characterised neatly by a recurrence relation or general form, then I can just take limits. Could someone point me there or at least explain what this 'wand' is supposed to be? Thank you very much for your help.
PS: I was also thinking of treating it as larger than a divergent sequence or series and then comparison test it.
Trying to find out if diameter and average pairwise distance of graph has a relationship
graph theory
Best Answer
Consider the graph $G_{m,n}$ with vertices $x_1,\dots,x_n$ and $y_1,\dots,y_{m}$ such that the edges are the ones of the form $\{x_i,x_j\}$ $\{x_i,y_1\}$ and $\{y_i,y_{i+1}\}$.
We can calculate the average distance precisely but I'd rather not. Notice when $m$ is fixed and $n$ goes to infinity the proportion of pairs of vertices that are of the form $\{x_i,x_j\}$ goes to $1$ and so the average distance goes to $1$. On the other hand the diameter is $m$, so when $n$ goes to infinity we have $\lim\limits_{n\to \infty} \frac{\operatorname{diam}(G_{n,m})}{\operatorname{apd}(G_{n,m})} = m$, so I believe there is no $c$ that fits the bill.