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

Question

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.

Answer 1

If I understand correctly, you call a cycle "minimum" if it has no chord.

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.

Here is an example of one such graph: