Partition a graph into $O(n)$ disjoint cycles and a forest

72 Views Asked by At

Is it true that there is a constant $c>0$ such that any graph on $n>2$ vertices can be partitioned into a forest and at most $cn$ disjoint cycles?

Source: https://artofproblemsolving.com/community/c6h487120p2729533 (contains a proof for $cn\log n$ instead of $cn$).