# The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles

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

• @FedorPetrov, sorry that was a typo. I will edit. – hbm Feb 3 at 19:20

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

• This line of reasoning was adapted and modified from one of @Misha Lavrov's answers in MSE – Mike Feb 4 at 1:34
• math.stackexchange.com/questions/3073345/… – Mike Feb 4 at 1:45
• could you please justify why the cycle are $O(log(L))$ – hbm Feb 5 at 21:01
• Sure. Let $G$ be a multigraph where every vertex has degree 3. Take any vertex $v$. Let $l$ be the length of the smallest cycle in $G$ . Then within distance 1 there have to be $m_1 \geq 3$ vertices. .... – Mike Feb 5 at 21:25
• Now, each of these vertices $u$ within distance 1 of $v$ has a multiset $N_u$ of $d(u)-1 \ge 2$ neighbours besides $v$ itself, and for there to be no cycles of length 5 or less, the $N_u$s cannot intersect each other--lest their be a cycle of length $\le 5$, $u$ cannot be in $N_u$ (lest their be a loop), and if $u'$ is another vertex of distance 1 from $v$ then $u'$ cannot be in $N_u$ either, lest their be a cycle of length 3. Furthermore every vertex in the multiset $N_u$ can only appear once lest there be parallel edges (cycle of length 2). – Mike Feb 5 at 21:35