If between every two vertices in graph $G$ exists a path of length at most $k$, prove that graph contains a cycle of length at most $2k+1$. It is known also that $G$ isn't a tree.
So we know that between every two vertices in graph exists a path of length at most $k$, so $G$ is connected, and it isn't a tree, so that means there exists a cycle.
In graph exists a vertex of degree $2$, let's call it $u$. Between $u$ and a vertex $v$ exists path of length $\leq k$. We know that between $v$, and a neighbor of $u$ exists also a path with length $\leq k$.
We started from $u$, went to $v$, and from $v$ went to a neighbor of $u$, and then back to $u$, which means I made a cycle of length $\leq 2k+1$. Is my approach good?
Best Answer
Hints.
Let $C$ be the shortest cycle of graph $G$. Choose two vertices on this cycle $u$ and $v$ so that the distance along the cycle between them is largest. Note that then this distance is at most $k$ (otherwise the cycle is not the shortest). From this, deduce that the length of the cycle is at most $2k+1$.
PS. For a triangle this statement is of course true.