How do I prove that for a graph G, I can always find a constant c>0 such that
$$
\frac{\text{diameter}(G)}{\text{average pairwise distance} (G)} > c
$$
where
$$
\text{average pairwise distance }= \frac{\sum_{v_1,v_2\in V}\text{distance}(v_1, v_2)}{\binom{n}{2}}
$$
Best Answer
If I'm not mistaken, $$ \operatorname{diam}(G) = \max\{\operatorname{dist}(v_1,v_2) : v_1,v_2 \in V\} $$ and $$ \operatorname{AvgPairDist}(G) \leq \max\{\operatorname{dist}(v_1,v_2) : v_1,v_2 \in V\} = \operatorname{diam}(G) $$ So $$ \frac{\operatorname{diam}(G)}{\operatorname{AvgPairDist}(G)} \geq \frac{\operatorname{diam}(G)}{\operatorname{diam}(G)} = 1 $$ ...or am I missing something?