3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ This line of reasoning was adapted and modified from one of @Misha Lavrov's answers in MSE $\endgroup$ – Mike Feb 4 at 1:34
  • $\begingroup$ math.stackexchange.com/questions/3073345/… $\endgroup$ – Mike Feb 4 at 1:45
  • $\begingroup$ could you please justify why the cycle are $O(log(L))$ $\endgroup$ – hbm Feb 5 at 21:01
  • $\begingroup$ 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. .... $\endgroup$ – Mike Feb 5 at 21:25
  • $\begingroup$ 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). $\endgroup$ – Mike Feb 5 at 21:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.