# Number of cycles in a graph?

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.

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.
• 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)!$ – Sasho Nikolov Mar 9 '13 at 21:45
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)$.