# On bounding the diameter of a undirected simple connected graph

This may be a something already there in literature but I am unable find it:

Given an undirected simple connected graph $G$ whose vertices has a degree at-least $d$ and $\ge c n^2$ edges, where $0 < c < 1/2$ is a constant, what is the upper bound on the diameter of $G$?

If this is known, any reference will be appreciated.

• $n$ is the number of vertices of the graph $G$? – Alex Ravsky Jun 1 '15 at 5:10

It seems the following.

I shall assume that $n$ is the number of vertices of the graph $G$. The asymptotical upper bound on $\operatorname{diam}(G)$ should be large, $\ge\simeq \frac 2d(1-\sqrt{2c})n.$ To show this, for an arbitrary number $D$ we construct a graph $G$ as follows. Consider a sequence $\{G_0, G_1,\dots, G_D\}$ of mutually disjoint graphs such that $G_0$ is isomorphic to the full graph $K_m$ on $m\ge d\ge 2$ vertices for some $m$ and every of the graphs $G_1,\dots, G_D$ is isomorphic to a graph $K_d$. Put as $G$ the union of all these graphs $G_i$. Since At last, in every $G_i$ pick arbitrary vertices $v_i\ne w_i$ an add to the graph $G$ edges $[v_0,w_1],[v_1, w_2], [v_2, w_3], \dots, [v_{D-1}, w_D]$.

Then $\operatorname{diam}(G)=2D+1,$ every vertex of the graph $G$ has degree at least $d$,

$$v(G)=m+Dd,$$

$$e(G)=\frac{m(m-1)}2+D\frac{d(d -1)}2+D.$$

Inequality

$$e(G)\ge cv(G)^2$$

is equivalent to

$$m^2-m+D(d^2 –d+2)\ge 2c (m+Dd)^2$$

Which yields an asymptotical (with $m\to\infty$ and $d$ fixed) lower bound

$$Dd\ge\simeq\left(\frac 1{\sqrt{2c}}-1\right)m,$$

that is $$D\ge\simeq\frac{1-\sqrt{2c}}{d}n.$$