Can the number of cycles in a graph (undirected/directed) be exponential in the number of edges/vertices?

I'm looking for a polynomial algorithm for finding all cycles in a graph and was wondering if it's even possible.


2 Answers 2


Assuming you mean simple cycles (otherwise the number is infinite) - yes, of course the number can be exponential: consider the complete graph on $n$ vertices, then every sequence of distinct vertices can be completed to a simple cycle. So you get at least $n!$ cycles.

Even if you ignore cyclic permutations of a cycle, this is still exponential: you can take only cycles of length $n/2$, and you have more than ${n\choose n/2}$ such cycles.

  • 2
    $\begingroup$ there are only $\leq n$ cyclic permutations of any cycle. you could also exclude any the reverse of any cycle, and you still have $\geq 0.5 (n-1)!$ $\endgroup$ Mar 9, 2013 at 21:45

The problem you want to solve is #CYCLE. Unless P=NP, it cannot be solved, for a proof look at the chapter on Counting Complexity in Arora and Barak. It is a gadget construction that reduces solving Hamiltonian path to #CYCLE and hence unless P=NP, Hamiltonian cycle - a NP-Complete problem cannot have a poly time solution.

As for the first question, as Shauli pointed out, it can have exponential number of cycles. Actually it can have even more - in a complete graph, consider any permutation and its a cycle hence atleast n! cycles. Actually a complete graph has exactly (n+1)! cycles which is $O(n^n)$.

  • 9
    $\begingroup$ You mean to say "it cannot be solved in polynomial time." That's a very different statement than "it cannot be solved" $\endgroup$ Dec 19, 2016 at 17:11
  • $\begingroup$ The gadget just shows a reduction from HAM to #CYCLE, how does that tell you of a way to count simple cycles? what if the graph has many cycles but not hamilton cycles? $\endgroup$
    – shinzou
    May 13, 2017 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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