Let $c(n,k)$ be the least integer such that if $G$ is a simple graph on $n$ vertices with $n + c(n,k) - 1$ edges then $G$ has $k$ edge-disjoint cycles. 


Clearly, $c(n, 1) = 1$ and it not very hard to prove that $c(n,2) \le 5$ (an exercise in Bondy's book.)


How does $c(n,k)$ depends on $n$ and $k$?



The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles
$O(k \log k)$ edges would suffice. So $c(n,k)$ is $O(k \log k)$.


We this by showing the following:



> 
> Thm 1: let $G$ be a graph on $n$ vertices with $n+K$ edges. There are $\theta(K/\log K)$ edge-disjoint cycles in $G$. 
> 
> 
> 


For the proof of Thm 1, we first define for every graph $G'$, the multigraph $f(G')$ formed from $G'$ by (a) taking the 2-core of $G$ and (b) then contracting each path of degree-2 vertices into an edge. Then 


1. If $G'$ has $K$ more edges than vertices, $f(G')$ has $L$ more edges than vertices for some $L \ge K$.
2. Every vertex in $f(G')$ has degree at least 3 so letting $L$ be as in 1. above, it follows that $f(G')$ has $O(L)$ vertices.
3. Every set of edge-disjoint cycle in $f(G')$ (even if the cycle is a loop or two parallel edges) corresponds to a set of edge-disjoint cycles in $G'$ of the same cardinality.


So letting $G$ be as in the top paragraph, set $H\_1 \doteq f(G)$, then as every vertex in $H\_1$ has degree at least 3 so only $O(L)$ vertices in $H\_1$. Thus there is a cycle $C\_1$ in $H\_1$ of length $O(\log L)$ [if you do not see why I can justify]. Remove the edges from $C\_1$ from $H\_1$ and call the resulting graph $H'\_1$. Then $H'\_1$ has at at least $L\_1= L-O(\log L)$ more edges than vertices, so does $H\_2 \doteq f(H'\_1)$. Thus there is a cycle $C\_2$ in $H\_2$ of length $O(\log L)$ [note that the number of vertices in $H\_2$ is no more than the number of vertices in $H\_1$ and is $O(L)$]. So remove the edges from $C\_2$ from $H\_2$ and call the resulting graph $H'\_2$. Then $H'\_2$ has at least $L\_2= L\_1-O(\log L)$ $=L-2 \times O(\log L)$ more edges than vertices, and so does $H\_3 \doteq f(H'\_2)$. And so on and so forth; for general $\ell$, define the graph $H\_{\ell}$ recursively: $H\_{\ell+1} = f(H\_{\ell} \setminus E(C\_{\ell}))$ where $C\_{\ell}$ is a shortest cycle in $H\_{\ell}$. Then $H\_{\ell}$ has at least $L\_{\ell} = L-O(\ell \log L)$ more edges than vertices.


Use the above line of reasoning to conclude that you will wind up with $C\_1,\ldots C\_M$ cycles for some $M \in \Omega(L/\log L)$. And so $G$ has $M \in \Omega(L/\log L) \subseteq \Omega(K/ \log K)$ edge-disjoint cycles and so Thm 1 follows.


\*\*As there are e.g., $K$-regular graphs on $n$ vertices where the smallest cycle has length $\theta\_K(\log n)$, Thm 1 above gives a lower bound that is asymptotically tight.




---


The following claim is added for completeness.



> 
> Claim 2: Let $H$ be a multigraph on $N$ vertices where every vertex is incident to at least 3 edges. Then $H$ has a cycle of length $O(\log N)$ [even if the cycle is a loop or two parallel edges].
> 
> 
> 


Proof: For each vertex $u$ let us denote by let $N^{\ell}(u)$ denote the multiset of vertices $u$ of distance precisely $\ell$ from $u$. So $N^1(u)$ denotes the multiset of neighbours of $u$ in $H$.


Now pick an arbitrary vertex $v$. Then for $\ell=1$, the set $N^1(v)$ must have $d\_H(v) \geq 3$ distinct vertices, lest there is a loop or parallel edges incident to $v$. 


We now claim that $N^2(v) \ge 2m\_1$ where $m\_1 \doteq |N^1(v)|$, lest $H$ has a cycle of length 5 or less. Indeed, for each $u \in N^1(v)$, the set $N^1(u)\setminus \{v\}$ (i) must have $d\_H(u)-1 \geq 2$ distinct elements [lest there be parallel edges], (ii) cannot contain $u$ itself [lest $H$ have loops], (iii) for any other $u' \in N^1(v)$ cannot intersect $N^1(u')\setminus \{v\}$ [lest $H$ have a cycle of length 5], and finally (iv) cannot intersect $N^1(v)$ [lest $H$ have a cycle of length 3]. So it follows from (iv) that every vertex in $N^1(u) \setminus \{v\}$ is in $N^2(v)$, and furthermore, from (i),(ii), and (iii): $m\_2 \doteq |N^2(v)|$ must be at least $\sum\_{u \in N^1(v)} (d\_H(u)-1) \geq \sum\_{u \in N^1(v)} 2 = 2m\_1$ distinct vertices.


By a similar line of reasoning, one can show for each $\ell$ the following:


\*\*\*\*$m\_{\ell+1} \doteq |N^{\ell+1}(v)|$ satisfies $m\_{\ell+1} \geq 2m\_{\ell}$ where $m\_{\ell} \doteq |N^{\ell}(v)|$, lest there is a cycle of length $2\ell+3$ or less. 


Indeed, each vertex $u \in N^{\ell}(v)$ has only one neighbor in $N^{\ell-1}$ [lest $H$ has a cycle of length $2\ell$ or less], no neighbours in $N^{\ell}(v)$ [lest $H$ has a cycle of length $2\ell+1$ or less] and so each such $u$ has $d\_H(u)-1$ distinct neighbours in $N^{\ell+1}$ [lest $H$ have parallel edges and so a cycle of length 2]. So for each $u \in N^{\ell}(v)$ it follows that $N^1(u) \cap N^{\ell+1}(u) = d\_H(u)-1 \ge 2$, and furthermore, if $u$ and $u'$ are distinct vertices in $N^{\ell}(v)$ then $N^1(u) \cap N^{\ell+1}(u)$ and $N^1(u') \cap N^{\ell+1}(u')$ are disjoint. So it follows that $m\_{\ell+1} \doteq |N^{\ell+1}(v)|$ satisfies $m\_{\ell+1} = \sum\_{u \in N^{\ell}(v)} (d\_H(u)-1)$ $\ge \sum\_{u \in N^{\ell}(v)} 2$ $\ge 2|N^{\ell}(v)| \doteq 2m\_{\ell}$.


Thus, it follows that for each $\ell$, here is a cycle of length $2\ell+3$ or less, or the following string of inequalities hold: 


$$m\_{\ell+1} \ge 2m\_{\ell} \geq 4m\_{\ell-1} \geq \ldots \ge 2^{\ell}m\_1 \ge 3 \times 2^{\ell}.$$


But there are only $N$ vertices so $m\_{\ell+1} \doteq |N^{\ell+1}(v)|$ must be no larger than $N$, which follows that for $\ell = \log N+1$ that $m\_{\ell+1}$ must indeed be smaller than $3 \times 2^{\ell}$ so there much be a sycle of length no larger than $2\log N + 5$ after all.


