# How many simple cycles can a graph with $n$ vertices and $m$ edges have?

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?

• If the rate of growth accelerates as more edges are added, it can't literally become exponential until we are only $O(n\log n)$ edges short of a complete graph. Is that inconsistent with what you know? – Brendan McKay Apr 17 '15 at 0:56
• @Brendan: To be honest, I did not spend too much time thinking about this, it was just obvious that the end becomes exponential. I am more interested in the beginning, like the function in Tony's answer, except that I want the minimum number of cycles. – domotorp Apr 17 '15 at 5:58
• I know what the domain and the range is but it is so had some time but I can get it done.(((: – user83660 Dec 4 '15 at 18:34

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)$.