Quick note, the method I am using for combining two cycles is just adding the edges and removing any edge in both cycle. Effectively, I am taking the exclusive or of their set of edges as long as the intersection of their set of edges is not empty.
I am working on cycle extraction for a project, and I have written code which will quickly extract a cycle basis (not necessarily the minimum) for some graph, G. I know that if my cycle basis has cardinality N, I would need to check $2^N – 1$ combinations to build an exhaustive list of cycles from this basis (check each cycle against all the combinations of other cycles).
However, I am curious if I can take some short cuts for specific cycle counts. It would be really helpful if I knew for a fact that combining cycles could only create larger cycles (which makes since to me, but my mathematical intuition is awful!)
For example, If my guess is correct, then every cycle basis for G must contain all the simple three cycles (because you could not get a three cycle by combining any other cycles). Also, If I wanted to look at 5 cycles I could then only consider the cycles in my cycle basis less than 5, etc…
Best Answer
Start with a $4$-cycle. Now add one diagonal edge, and subdivide that edge into $n$ edges by adding $n-1$ vertices. You now have two $(n+2)$-cycles that share $n$ edges; adding them will produce the original $4$-cycle no matter how big $n$ is. Here is an example with $n=4$.