Skip to main content
1 of 5
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, a bound of the form $\Omega(\frac{d}{\log d})$ follows from the following theorem.

Theorem. For every integer $k$, every graph $G$ either contains $k$ edge-disjoint cycles, or a set of edges $X$ of size at most $(2+o(1))k \log k$ such that $G-X$ is a forest.

This is actually an exercise in Diestel's graph theory textbook. Since the minimum number of edges to remove to make a graph acyclic is $d$ (take the complement of a spanning tree), the bound follows. As noted by Gjergji Zaimi in a comment to the other answer, this bound is best possible 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 survery paper of Raymond and Thilikos.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187