Connected graph with minimum degree $k \geqslant 3$ and path between two vertices In a connected graph with every vertex has a degree of at least $k \geqslant 3$, there exist a path $P$ between any two vertex $x,y$ such that $|V(P)| \leqslant \frac{3 |V(G)|}{k−2}$.
My thought is the path can have only one $N(x)$, and one $N(N(x))$, so on and so forth, but I don't know what to do beyond this point.
 A: I will show that, in a connected graph where every vertex has degree at least $k\ge3$, any two vertices $x$ and $y$ are connected by a path $P$ with $|V(P)|\le\frac{3|V(G)|-2}{k+1}\lt\frac{3|V(G)|}{k-2}$.
Let $G$ be a connected (finite, simple) graph with minimum degree $\delta(G)\ge k\ge3$. Consider any vertices $x,y\in V(G)$. The case $x=y$ is trivial, so we assume $x\ne y$. Let $P$ be a minimum length path from $x$ to $y$. Let $|V(G)|=n$ and $|V(P)|=p$. Let $e$ be the number of edges between $P$ and $V(G)\setminus V(P)$.
Since each endpoint of $P$ has at least $k-1$ neighbors in $V(G)\setminus V(P)$, while each internal vertex of $P$ has at least $k-2$ neighbors in $V(G)\setminus V(P)$, we have
$$e\ge2(k-1)+(p-2)(k-2).\tag1$$
On the other hand, since each vertex in $V(G)\setminus V(P)$ has at most $3$ neighbors in $V(P)$ (or else we could use it to get a shorter path between $x$ and $y$), we have
$$e\le3(n-p).\tag2$$
From $(1)$ and $(2)$ we get
$$2(k-1)+(p-2)(k-2)\le3(n-p)$$
which simplifies to
$$(k+1)p\le3n-2$$
and finally
$$p\le\frac{3n-2}{k+1}.$$
P.S. In the same way you can show that, if $G$ is a finite simple graph with minimum degree $\delta(G)\ge2$, then $G$ contains a cycle of length $\le\max\left\{4,\left\lfloor\frac{|V(G)|}{\delta(G)-1}\right\rfloor\right\}$.
