Well, to begin with, we may reduce this question to one about graphs with minimum degree $3$.
Suppose that a vertex in $G$ has degree only $2$. Then we may "smooth out" that vertex: delete it from the graph, replacing it by an edge joining its two neighbors. If we prove that the new graph $G'$ has a cycle with at most $2\lg (n-1)+1$ vertices of degree $\ge 3$, then the original graph $G$ had a cycle with at most $2\lg (n-1)+1$ (and therefore at most $2 \lg n+1$) such vertices. After all, even if the cycle used the edge where the deleted vertex used to be, adding the vertex back in by subdividing that edge won't change tha number of vertices of degree $\ge 3$ on the cycle.
This smoothing process can be done any number of times. We might eventually get a $K_3$ as a connected component (in which smoothing out any vertex leaves a multigraph, which is a problem, but which also contains a cycle with no vertices of degree $\ge 3$). Otherwise, we'll be left with a graph that has no vertices of degree $2$ to smooth out.
In such a graph, from any vertex $v$ there are at least $3 \cdot 2^{k-1} > 2^k$ paths of length $k$ starting at $v$. (Or at least there are that many non-backtracking walks, which go to a vertex and then keep going to a vertex that's not the one they arrived from. But if they repeat a vertex, then we immediately get a cycle shorter than $k$ and we're done, so we assume they are paths.) Take $k = \lceil \lg n \rceil$; then there are more than $n$ such paths, so by the pigeonhole principle two of them must share an endpoint. This gives us a path with at most $2k+1$ vertices.
Best Answer
Consider a vertex of minimal degree. If the degree was $1$, then we're done by induction if we remove that vertex. Otherwise, the minimal degree in the graph is at least $2$. Take a longest path $v_0 v_1 \dots v_k$; then $v_0$ has degree $2$ or higher, so the only way this can be a longest path is if $v_0$ is connected to some other $v_i$ than $v_1$. (If not, if $v_0$ is connected to $x$ which is not a $v_i$, then we could extend the path by adding $x$.) So we have found a cycle.
Why is there a longest path? There is certainly a path of length $1$ (pick any vertex!). There are only finitely many paths, since there are only $|V|$ vertices. So we can just list the paths, and their lengths; at least one of them will have longest length (because every finite set has a maximum).
Question for you: where have we used that the graph was connected?