ELMO SL 2011 C5

Prove there exists a constant $c$ (independent of $n$ ) such that for any graph $G$ with $n>2$ vertices, we can split $G$ into a forest and at most $cf(n)$ disjoint cycles, where

a) $f(n)=n\ln{n}$ ;

b) $f(n)=n$ .

David Yang.