Suppose that we have the complete graph $K_5$ and we remove two triangles. I see that we always get a cycle of length $4$ but I am not sure how to prove this.
If we remove one $K_3$ then for the second $K_3$ we have to use at least one of the vertices of the first one, since we only have $5$ in total. So this vertex has degree $2$ already in the decomposition... I don't know where to go from here.
When I say "remove" I mean disregard the edges that the triangles use.
When we remove a triangle, the degree of each vertex involved decreases by $2$. So all degrees are even. Furthermore, the two triangles may not share en edge. So every vertex is involved in some triangle. Therefore, there are no vertices of degree $4$.
Putting this together, the final graph has all vertices of degree $0$ or $2$. Therefore, it is a disjoint union of cycles. The final graph has $4$ edges, so it must be a single $4$-cycle. (The smallest disjoint union of two nonempty cycles has $6$ edges.)