I want to prove that for a graph with $n$ vertices, the size of the largest set of cycles that don't share edges with each other is at least $\frac{|E(G)| - |V(G)|}{2\lfloor \log_2(n+1)\rfloor}$.
It is trivial to prove this for all forests and trees. I can also observe that if we can prove this inequality for all graphs with a spanning tree that's at least binary (degree at least 3 for all non-leaf vertices), then we can also prove this inequality for all graphs in general (if there are long chains of vertices, then we can just remove all vertices in that chain except for the two ends, and that won't change $|E(G)| - |V(G)|$). I can also observe that $2\lfloor \log_2(n+1)\rfloor$ is an upper bound for the length of any cycle that have only 1 edge not in the spanning tree (and all other edges are shared with the spanning tree). I also observed that any such "1 edge not in tree" cycle correspond to a subtree of the spanning tree (if we remove the extra edge). I feel like I should use some property of the subtrees to determine if two cycles share an edge, but I can't find an easy way. Is there any suggestions on how I can proceed?
While the problem is about graphs, since my solution involves trees, I added the trees tag in case there are some specific techniques for trees that I can use.