# Given a graph G, what is the maximum number of "minimum" cycles it could have?

In graph G: a cycle $$A$$ is a subcycle of cycle $$B$$ if there exists vertices $$c$$ and $$d$$ such that:

• $$cd$$ is an edge of $$A$$.
• $$F$$ is the resulting path of $$A$$ after removing the edge $$cd$$.
• $$E$$ is a path from $$c$$ to $$d$$ of length at least $$2$$, and the cycle $$B$$ consists of the edges in $$E$$ and $$F$$

For example:

In the graph consisting of edges: 1,2 2,3 3,4 4,1 1,3 (with vertices 1-4), then:

3,4 4,1 1,3

and

1,2 2,3 1,3

are both subcycles of

1,2 2,3 3,4 4,1

A cycle is minimal if it has no subcycles.

Given a graph G, what is the worst-case (maximum) number of minimal cycles it could have???

My thought is a complete graph would have each triplet of vertices a minimum cycle, therefore about n^3 but I don't know if that's right

The computer science application of this is:

To compute a Hamiltonian cycle, you could first start with a minimum cycle and then see if you can replace an edge in the cycle with a path of length at least 2 (finding a cycle we're a subcycle of). If you do this over and and over get lucky each time, you will end up with a Hamiltonian cycle.

Then the number of minimum cycles can be exponential. As an example, start from a graph containing a single cycle $$C$$ and replace each edge $$e = (u,v)$$ with two "split" vertices $$x_e, y_e$$ and the edges $$(u, x_e), (x_e,v), (u, y_e), (y_e,v)$$.
Notice that, once you choose one of $$x_e$$ and $$y_e$$ for each edge $$e$$, you can build a chordless cycle that traverses exactly all original vertices of $$C$$ and all the chosen split vertices.
The resulting graph has $$3n$$ vertices and $$2^{n}$$ minimum cycles. 