I don't think that it is hard problem. My answer is 3(n-2)+1. Is that correct?

yes Dear myth it is right. you used induction to complete the solution?

Yes, I used induction, but it is not main part of solution.

Dear myth may I have look at your solution?

Hello, dear sam-n! Maybe it works. Suppose contrary. Let v₁,...,v_n are vertices and A={v₁,...,v_k} - minimal cycle (!). It is obvious that subgraph B={v_k+1,...,v_n} is a union of trees. 1. $k\geq 4$. It follows that each vertice v_k+i have 2 or less edges to v₁,...,v_k. Let us count number of all edges in this case: $|A| + (|B|-1) + 2\cdot |B| \leq k + (n-k-1) + 2(n-k-1) = 3n-3k-3 < 3n-5$ - contradiction. 2. k=3. Let us show there is vertices v_s (s>3) such that $|v_s|\leq 3$. Suppose opposite. Note that each dangling vertices of B has three egdes to A (!). a) Suppose B contains at least two trees C and D, and |C|>1. In this case D has dangling vertices and C has at least two dangling vertices. Now it is easy to construct two disjoint cycles. b) Suppose B is tree, u and v are dangling vertices, w is intermediate vertices between u and v (w exists because |B|>2). Since |w|>3 there are third dangling vertices in B or there are edge from w to A - in both cases we construct two disjoint cycles. c) Suppose B contains only trivial trees (i.e. single-vertice trees). Then each vetrices of B has degree 3. Suppose |v|=3. Exclude v from graph and apply induction. Example for 3(n-2) is a case 2.c).

I have looked through solution. And it seems correct! Though it have been lying in Unsolved Section for 9 months! Comments?

That's what I told you : After some times, a problem is out of mind, so moderators do not think to move it... Pierre.

I think we can't move it if there are no comments on problem. Especially, if problem is not easy.