Prove that for a simple connected graph $G$ given inequality is true: $$ \operatorname{diam}(G) \cdot \delta(G) < 3n $$
where $\operatorname{diam}(G)$ is the diameter of graph $G$, $\delta(G)$ is the minimum degree of the graph $G$ and $n$ is the number of all vertices in $G$
I've been trying to solve this problems for a very long time, and I still don't. Could anybody help.
Many thanks.
Let $a_0a_1\ldots a_D$ be a path of length $D=\operatorname{diam}(G)$ determining the diameter of $G$ (i.e. there is no shorter path from $a_0$ to $a_D$. For $0\le i\le D$, let $f(i,1),\ldots,f(i,\delta(G))$ be distinct neighbours of $a_i$ (this is possible by definition of $\delta$). This gives us a map $f$ from $\{0,\ldots,D\}\times \{1,\ldots,\delta(G)\}$ to the set $V$ of vertices of $G$.
Claim: For each vertex $v$, there are at most three pairs $(i,j)$ with $f(i,j)=v$.
Proof: Assume $v:=f(i,j)=f(i',j')=f(i'',j'')=f(i''',j''')$ with four different pairs $(i,j), (i',j'), (i'',j''), (i''',j''')$. Then $i,i',i'',i'''$ are pairwise distinct because we selected distinct neighbours in the definition of $f$. Wlog. $i<i'<i''<i'''$, hence $i'''>i+2$. The path $a_0\ldots a_iva_{i'''}\ldots a_D$ is obtained by replacing at least two vertices (namely at least $a_{i'}$ and $a_{i''}$) with a single vertex, hence it is shorter than $D$, contradiction. $_\square$
As a consequence $$3n\ge (D+1)\cdot \delta(G).$$
