Skip to main content
4 of 5
added 26 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, a bound follows from the following theorem. For a graph $G$, let $\nu(G)$ be the maximum number of edge-disjoint cycles, and let $\tau(G)$ be the minimum size of a set of edges $X$ such that $G-X$ has no cycles.

Theorem. There exists a function $f(k)=O(k \log k)$ such that for every graph $G$, $\tau(G) \leq f(\nu(G))$.

This is actually an exercise in Diestel's graph theory textbook. In your context, $\tau(\Gamma)=d$ (take the complement of a spanning tree), so we get $\nu(\Gamma) \geq f^{-1}(d)$. As noted by Gjergji Zaimi in a comment to the other answer, this bound is best possible (up to a constant factor) due to a classic example of Erdős and Pósa. Indeed there is huge body of related work, which are all called "Erdős-Pósa theorems." See this survey paper of Raymond and Thilikos or this webpage for more information.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187