See http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_boros_caro_yuster-hpgr_covers.pdf for asymptotic (better) bounds.

@mavropnevma: But it's a total overkill, don't you think? I mean this article. I agree, as shown, it's the best possible upper bound. But could you give a sketch how this article would help a student to manage this problem on a competition? Now, the first think that occurred to me reading the problem was: "spanning tree". Consider a spanning tree of the given graph. It contains $n-1$ edges. Now prove that adding $n/2$ additional edges will raise two cycles of equal length. Unfortunately this idea couldn't drop the bound under $3n/2$(without getting too complicated) but it's more than enough to solve this problem.

dgrozev wrote: @mavropnevma: But it's a total overkill, don't you think? I mean this article. I agree, as shown, it's the best possible upper bound. But could you give a sketch how this article would help a student to manage this problem on a competition? Now, the first think that occurred to me reading the problem was: "spanning tree". Consider a spanning tree of the given graph. It contains $n-1$ edges. Now prove that adding $n/2$ additional edges will raise two cycles of equal length. Unfortunately this idea couldn't drop the bound under $3n/2$(without getting too complicated) but it's more than enough to solve this problem. @dgrozev Can you explain your solution a little more?With this method I can get to the bound in the problem and even somethings better but how do you get$\frac{3n}{2}$?Thanks in advance.

Let $T$ be the spanning tree of the given graph $G$, obtained by depth first search algorithm. So, the edges in $E':=E(G)\setminus E(T)$ are not cross edges of $T$. Let $e=v_1v_2\in E'$, thus $v_1$ and $v_2$ are compatible with respect to $T$ and suppose $v_1<v_2$. For any such $e\in E'$ map $e$ to the path $p(e)$ in $T$ connecting $v_1$ with $v_2$. Now, let $|E'|=c\cdot n$, where $c$ is a constant (imagine $c=1/2$) and suppose there are no two cycles in $G$ with equal lengths. Since $v_1 p(e)v_2v_1$ is a cycle, for each $e\in E'$ , it follows all paths $p(e),e\in E'$ have distinct lengths. For any set of $2\sqrt{n}$ paths $p(e),e\in E'$ , there are two of them which intersect each other. Indeed, since their lengths are all distinct, their total length is at least $\sqrt n (2\sqrt n +1)>n-1$ , which means some two of them intersect, since the total length of the tree $T$ is $n-1$. Further, we start with the set of all paths $P:= \{p(e):e\in E'\}\}$, then take two intersecting paths, remove them and for the remaining ones we apply it again till there remains less than $2\sqrt n$ paths. Thus, we construct at least $m:=cn/2-\sqrt n$ pairs $(p'_i,p''_i), p'_i,p''_i\in P, p'_i\cap p''_i\neq \emptyset, i=1,2,\dots,m$. Let's estimate the number of all cycles. Each $p(e),e\in E'$ forms a cycle $v_1p(e)v_2v_1$. Any pair $(p'_i,p''_i)$ forms additional cycle. Indeed, suppose $p'_i=u'\dots v'$ and $p''_i=u''\dots v''$ and $u'<u''$. There are two possibilities: either $v'$ and $v''$ are comparable or they aren't. In both cases (one can check) there is a cycle different from $u'p'_iv'u'$ and $u''p''_iv''u''$. Assuming there are no cycles with equal lengths, all the constructed cycles are distinct and their number is at least $cn+cn/2-\sqrt n$. So, if $c$ is slightly bigger than $2/3$ it will bring to a contradiction, since the largest possible cycle has length $n$. To drop $c$ to something like $1/2$, we proceed with constructing additional cycles. Consider the sets of paths $P':=\{p'_i,i=1,2,\dots,m\}\}$, $P'':=\{p''_i,i=1,2,\dots,m\}\}$. We have $|P'|=|P''|=m\sim cn/2$. Applying the above construction with respect to $P'$ and then $P''$ we can bring in additional $\sim m/2+m/2=m\sim cn/2$ pairs of intersecting paths. The number of all cycles then is at least $cn+cn/2+cn/2-3\sqrt n=2cn-3\sqrt n$. Hence, if $c$ is slightly bigger than $1/2$ and $n$ large enough, we get a contradiction. Remark. I don't remember exactly what was my argument some five years ago, but for sure the first part was to take a spanning tree with all additional (n/2) edges along the tree, without cross edges. In that way we may associate the natural cycles with the paths along the tree formed by their end points.

I don't see how dgrozev wrote: Applying the above construction with respect to $P'$ and then $P''$ would help solve the issue of making $c$ slightly bigger since both $P'$ and $P''$ are paths, and do not contain any cycles. If someone could iterate the first few steps of such a construction, that would be great.

In the terms of the problem statement, section (b), we can drop $\frac{7n}{4}$ up to any $(1+\varepsilon)n$ for any $\varepsilon >0$. It was a RMM 2019 problem (by Fedor Petrov) and I used there the same approach as above to show $n+O(n^{3/4})$ does the job.