Return to Answer

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.

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. Note that for a connected graph $G$ with $H^1(G) \cong \mathbb{Z}^d$, we have $d = \tau(G) \geq \nu(G)$, so $\nu(G) \gg d$ is impossible (although I assume you were hoping for $\nu(G) \in \Omega(d)$). This is also impossible, but we can get close.

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 other words, $\nu(\Gamma) \geq f^{-1}(d)$. As noted by Gjergji Zaimi in a comment to the other answer, this bound is actually 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.

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. Since $\tau(G)=d$ (take the complement of a spanning tree), we get $\nu(G) \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.

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.

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(\mu(G))$.

This is actually an exercise in Diestel's graph theory textbook. Since $\tau(G)=d$ (take the complement of a spanning tree), we get $\nu(G) \geq f^{-1}(d)$. 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 survey paper of Raymond and Thilikos or this webpage for more information.

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. Since $\tau(G)=d$ (take the complement of a spanning tree), we get $\nu(G) \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.