# Graphs with many cycles and doubled cycle minors

This one isn't my problem – it came from MathOverflow – but it's frustrating me that I haven't been able to solve it, so I hope by reposting it here I can get some more attention to it and maybe even a solution.

Here are some examples of graphs for which the number of cycles is large relative to the size of the largest doubled cycle minor:

A biconnected graph with no length-3 doubled cycle minor must be either a subdivision of \( K_4 \) or a series-parallel graph in which one of the two arguments to each series composition is a path. All such graphs have \( O(n^2) \) cycles.

In outerplanar graphs, the length \( k \) of a doubled cycle minor is the number of leaves of the dual tree. Each cycle can be formed by pruning some branches of the tree, and there are at most \( k \) branches to prune, so there are \( O(n^k) \) cycles in the outerplanar graphs with no doubled \( k \)-cycle minor. For instance, the outerplanar graph below has four leaves.

The complete bipartite graph \( K_{k,n} \) (for \( k \le 2n \)) has maximum doubled cycle minor length \( k \) and \( O(n^k) \) cycles.

In complete graphs, the length of a doubled cycle minor is approximately \( 2/3 \) the number of vertices. (Each edge contraction can double only two of the edges of a cycle.) The number of cycles is factorial in the number of vertices, so the exponent of the number of cycles (as a polynomial in \( n \)) is also linear in \( n \).

Form a tree with height \( \log_2 k \) and branching factor \( b \) (possibly much larger than \( k \)). Connect each node to all its ancestors and connect the set the children of each node by a spanning tree. If we didn't include the spanning trees, the result would have low tree-depth, causing all of its cycles to have length at most \( k \), from which it follows that there are \( O(n^k) \) cycles and maximum doubled cycle length \( k \). The spanning trees don't significantly increase the number of cycles (you can use at most one path per spanning tree in a cycle, and each cycle touches at most \( k \) of these trees) and for the same reason doesn't significantly increase the length of the longest doubled cycle minor.

Somehow I have the feeling that the last example, based on tree-depth, is on the right track. For minor-closed graph families, having no large cycle minor is the same as each biconnected component having bounded tree-depth, so having no large doubled cycle minor should be the same as having some structure like tree-depth but a little more complicated. But I can't prove anything of the sort.

ETA 2014-04-10: Solved, negatively, by a planar bipartite permutation graph.

### Comments:

**None**:

**2014-04-05T20:16:01Z**

May I ask with which program do you generate these beautiful graph figures?

**11011110**:

**2014-04-05T20:34:42Z**

Thanks — I drew them using Adobe Illustrator. The vertex placement was done by hand rather than automatically.