[Math] How many simple cycles can a graph with $n$ vertices and $m$ edges have

Question

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have.
For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is $m-n$, then after a while it starts to grow exponentially with $m$.
What is known about this function?

Answer 1

To supplement Igor's answer, here is some more information on the maximum number of cycles a graph on $n$ vertices with $m$ edges can have. I apologize that this does not answer your question. Entringer and Slater considered this problem in their paper On the Maximum Number of Cycles in a Graph.

Let $G$ be a simple connected graph with $m$ edges and $n$ vertices. It is useful to re-parametrize by letting $d=m-n+1$, and defining $\psi(d)$ to be the maximum number of cycles of a graph with $m-n+1=d$. They observed that since $d$ is the dimension of the cycle space of $G$, $\psi(d) \leq 2^d-1$. On the other hand, they showed that the Möbius ladders imply that $\psi(d) \geq 2^{d-1}+d^2-3d+3$. Using exhaustive computer search they also determined $\psi(d)$ for all $d \leq 8$, and conjectured that the lower bound is essentially the right answer for $\psi(d)$.