number of cylces in a graph

Consider a connected graph with e edges and v vertices, let x = e - v

for a given x what are the maximum and minimum number of cycles a graph can have?

Examples:

x = 0 the maximum number of cycles is 1 and the minimum is 1

x = 1 the maximum number of cycles is 3 and the minimum is 2

Is there a general formula for the max and min for a given x?

For the minimum I think it would be x+1. For the maximum I found a lower bound of (x^2+3x+2)/2

This lower bound can be found using the graph with edges {a,b,c,d,e ...} and vertices {(a,b) (c,a) (c,b) (d,a) (d,b) (e,a) (e,b) ... }

every additional vertex is attached to a and b and no others.

its graph looks like this:

• Forgot to mention that the graph must be connected – mathew May 15 '16 at 7:28
• I think you can edit your own question; maybe you want to edit and add the connectedness to the question body? – awllower May 15 '16 at 7:30
• thanks, didn't know how to do that – mathew May 15 '16 at 7:58

For a simple connected graph observe that there exists a maximum tree. A maximum tree is maximum acyclic too i.e adding an extra edge with the tree will give you a cycle. So now just count for a given tree how many extra edges do you have which are not in that tree. All those edges will give you at least one different cycle.

For a cnnected graph with $v$ many vertices, the cardinality of maximum tree would be $v-1$. So number of cycle would be $\geq e-v+1=x+1$.

I don't think mathews bound is right. Consider two triangle and attach them together by using an extra edge. So for this graph $x=1$ but it has only $2$ cycle, but according to mathews calculation it has at least 3 cycle.

I also found some interesting answer related to this, where it is suggested that this is still an open question. see here https://mathoverflow.net/questions/203119/how-many-simple-cycles-can-a-graph-with-n-vertices-and-m-edges-have

• I think it is possible to have more cycles then x+1. – mathew May 15 '16 at 20:06
• Yes, I said $\geq$, I give a lower bound. – Anubhav Mukherjee May 15 '16 at 20:07
• For example, verticies {a,b,c,d} and edges {(a,b),(b,c),(c,d),(a,d),(b,d)} – mathew May 15 '16 at 20:08
• This would have 3 cycles: abd and bcd – mathew May 15 '16 at 20:08
• I was looking for a formula for the maximum not just a lower bound – mathew May 15 '16 at 20:09

This is not a solution, but an extended comment related to the maximal number of cycles.

The complete graph with $n$ vertices, ie with edges between all pairs of vertices, has $e=n(n-1)/2$ edges, hence $x=n(n-3)/2$. So, let's count the cycles.

We can construct a $k$-cycle from any list $v_1,\ldots,v_k$ of distinct vertices: we can pick these vertices in $n(n-1)\cdots(n-k+1)$ different ways. However, each $k$-cycle can be represented in this way in $2k$ different ways: we may start at any of the $k$ vertices of the cycle, and go in either direction. Hence, summing over $k$ from $3$ to $n$, the number of distinct cycles is $$\sum_{k=3}^n\frac{n(n-1)\cdots(n-k+1)}{2k}$$ which is greater than $(n-1)!/2$ and this increases hyperexponentially in $n$. It then follows that the maximal number of cycles can also be hyperexponential in $x$ since $x$ is quadratic in $n$.

• why do you start the summation at k=4 rather than at k=3? – mathew May 17 '16 at 1:04
• @mathew: Typo. Will correct. – Einar Rødland May 17 '16 at 1:11