1
$\begingroup$

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: enter image description here

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

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.