Return to Answer

By a similar line of reasoning, one can show for each $\ell$, that $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 $m_{\ell+1} \ge 2m_{\ell} \geq 4m_{\ell-1} \geq \ldots 2^{\ell}m_1 \geq 3 \times 2^{\ell}$ lest there is a cycle of length $2\ell+3$ or less. But there are only $N$ vertices so $m_{ell+1}$ 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.

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.

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$, that $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 $m_{\ell+1} \ge 2m_{\ell} \geq 4m_{\ell-1} \geq \ldots 2^{\ell}m_1 \geq 3 \times 2^{\ell}$ lest there is a cycle of length $2\ell+3$ or less. But there are only $N$ vertices so $m_{ell+1}$ 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.

$O(k \log k)$ edges would suffice.

We show 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.

$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.