# Do graphs with large number of cycles always contain large necklace minor?

Let "$k$-necklace" denote the (multi)graph obtained from a cycle of length $k$ by duplicating every edge.

Note that the number of cycles in $k$-necklace is at least $2^k.$

Question : Suppose a simple graph $G$ contains at least $n^k$ cycles where $n$ is the number of vertices of $G$. Is it possible to obtain a $\Omega(k)$-necklace from $G$ by a sequence of deletion and contraction of edges?

I would be equally happy if one can guarantee $\sqrt k$-necklace (or $k^\alpha$ necklace for some $\alpha > 0$) instead of $k$-necklace.

• Is $G$ an honest graph? If it is a multigraph as well, this may be impossible. – Alex Degtyarev Mar 21 '14 at 9:59
• If you take a tree with $n$ vertices and duplicate a single edge $n^k$ times, then there are $\binom{n^k}{2}$ cycles, but no $k$-necklace minors (provided $k \geq 3$). – Tony Huynh Mar 21 '14 at 10:37
• yes you are right. $G$ should be a simple (or honest) graph – Raghav Kulkarni Mar 21 '14 at 16:50
• Don't cycles of length 2 count? In which case a k-necklace contains more than 2^k cycles for k>2. Gerhard "Ask Me About System Design" Paseman, 2014.03.21 – Gerhard Paseman Mar 21 '14 at 17:41
• @Zsbán Ambrus: $n$ is the number of vertices, so it is not possible to have $2^n$ components. Raghav: I haven't been able to solve your problem, but I found it interesting enough to make a blog post about it: see 11011110.livejournal.com/286355.html – David Eppstein Apr 5 '14 at 7:20

I believe Anton Malyshev's answer to Do graphs with large number of paths contain large chain minor? answers this question as well. It is a bipartite planar permutation graph in which there are $n/2$ pairs of vertices $u_i$ and $v_i$, with edges from both $u_i$ and $v_i$ to $u_{i+1}$ and $v_{i+1}$ but not to each other. It contains large chain minors (paths with each edge doubled), but its cycle minors can have at most four doubled edges, two each at their minimum and maximum indices. Its number of cycles is $\Theta(2^{n/2})=n^{\Theta(n/\log n)}$. If $G$ is a simple graph then this can fail for small $n$ (for $\alpha=1$). A $k$-necklace can only be a minor of a graph $G$ if $G$ has at least $3k/2$ vertices (as one vertex-identification can be responsible for at most two of the doubled edges in the necklace). But the complete graph on $4k/3$ vertices has more than $(4k/3)^k$ cycles.
• yes, you are correct. the exact bound does not hold. I would like asymptotic bound, i.e., $\Omega(k)$-necklace (or $\sqrt k$ or anything polynomial in $k$) – Raghav Kulkarni Mar 21 '14 at 16:56