In order to prove a) we use two facts: Fact 1. Every gtaph $G$ contains a cycle of length at least $\delta(G)+1$, providing $\delta(G) \geq 2$. Here $\delta(G) = \min_{v\in V(G)} \deg(v)$. Fact 2. Every graph $G$ has a subgraph $H$ with $\delta(H) > \frac{|E(G)|}{|V(G)|}$. Both propositions can be found in R.Diestel's "Graph Theory". These facts imply: Proposition 1. If $\frac{|E(G)|}{|V(G)|} \geq 2$ then $G$ contains a cycle with length at least $\frac{|E(G)|}{|V(G)|}.\, \square$ Let now denote $m=E(G)$. Proposition 1 yields that there exists a cycle with length at least $\frac{m}{n}$. Delete all edges of this cycle and there will remain $m_1=m(1-\frac{1}{n} )$ edges. So after $k$ steps there will remain $m_k= m(1-\frac{1}{n})^k$ edges. Here $m = O(n^2)$, so proceeding in this way guarantees $m_k$ will become $O(n)$ after $O(n\ln n)$ steps, which means that after $O(n\ln n)$ steps there will be no cycles to be removed (a forest will remain). Thus we proved a). Comment. Directly applying this method can not prove b), so it needs some fresh idea or somehow essentially to improve the above algorithm. I am very curious about the algorithm which could yield $O(n)$ cycles and a forest.

dgrozev wrote: Comment. Directly applying this method can not prove b), so it needs some fresh idea or somehow essentially to improve the above algorithm. I am very curious about the algorithm which could yield $O(n)$ cycles and a forest. Hmm, David does not seem to remember his solution. All I know is that it involved Vinogradov's theorem, i.e. the fact that every sufficiently large odd number is the sum of three primes... perhaps he made a mistake, I dunno.

Could anyone post a solution to b)? Knowing that it's connected with Vinogradov's theorem does not help me......

It was pointed out to me some time ago that part b would imply the Erdos-Gallai cycle decomposition conjecture which is still open, so I'm not sure if dyang fakesolved or if he is just a genius