# Graph Theory(Avg. Distance and Diameter)

When we consider a graph we always want one term to get compact information about it's structure.Average distance and diameter can serve that purpose,but most of the time they turns out to be approximately equal.Can we have atleast one example where diameter is 3 times average distance in graph?

-
i got some idea from Artem Kaznatcheev in link but please someone explain 'm not getting it properly... –  user997704 Jan 27 '12 at 4:38
please someone answer it..stuck since last hour... –  user997704 Jan 27 '12 at 4:53
in general, you should try to explain what you tried already and where you are stuck. Especially for hw questions. –  Artem Kaznatcheev Jan 27 '12 at 5:05

As I commented on cstheory just take $K_n$ and glue a path $P_{2m}$ from one of the vertices in $K_n$. The diameter is obviously $2m$, by looking at the distance between any vertex (except the one you glued to) in $K_n$ to the vertex at the end of the path $P_{2m}$.

Now, lets upper bound the average distance $\langle d \rangle$, we know that:

$$\langle d \rangle \leq \frac{1}{n(n - 1)/2 + (2m - 1) + (2m - 1)n}\Big(n(n - 1)/2 + (2m - 1) + 2m(2m - 1)n\Big)$$

Where the normalization is by the number of edges in the graph and the first summand is sum of distances between vertexes in $K_n$ the second is for $P_m$ and the third is an upper bound on the distance between vertexes in $K_n$ and vertexes in $P_m$ (since they are each at a distance of at most $2m$ from each other).

The above equation simplifies to:

$$\langle d \rangle \leq 1 + \frac{2(2m - 1)^2}{n - 1 + \frac{2}{n}(2m - 1) + 2(2m - 1)}$$

For $m \geq 1$ and $n \geq 2(2m - 1)(2m - 2) \in \Omega(m^2)$ this becomes:

$$\langle d \rangle \leq 2$$

Thus, you get the diameter $m$ times longer than the average distance.

-