There is a natural iterative approach.
Until $G$ contains no cycle, do the following:
- Select a cycle $\gamma$ in $G$.
- Add $\gamma$ to $C$, and remove it from $G$. Here, by adding and removing I mean adding and removing edges - the formulation suggests that you want to decompose edges of $G$ (rather than vertices).
Once there are no cycles in $G$, it has to be a sum of trees. (It is well known that a connected acyclic graph is a tree, and accordingly a not-necessarily-connected acyclic graph is a sum of trees). Thus, you can denote whatever remains of $G$ by $T$ and you are done.
From the construction it is clear that $C$ is a sum of cycles, and we have shown that $T$ is a sum of trees. One thing that remains to be seen is that the cycles in $C$ are vertex-disjoint. Suppose otherwise, i.e. there are two cycles $\gamma$ and $\gamma'$ in $C$ that have a common vertex $v$. For the sake of concreteness, assume $\gamma$ was added to $C$ before $\gamma'$. At first, $v$ had at most $3$ entering edges. Since we deleted two edges entering $v$ when $\gamma$ was added to $C$, after that step $v$ had at most $3-2 = 1$ entering edge. Thus, it can't lie on any cycle after that step, since belonging to a cycle requires degree at least $2$.