I wish to construct an unweighted, undirected graph on $n$ nodes that maximizes the number of minimal cycles of size $\ge k$. What is known about this problem? How many cycles can I squeeze in?

Additionally, how does the problem change if I require that my graph has $\ge m$ edges?

Clarification: I care purely about the existence of a many-cycled graph; it doesn't need to be efficiently constructable.

  • $\begingroup$ Crossposted on mathoverflow. $\endgroup$ Feb 11, 2014 at 11:20
  • $\begingroup$ By minimal cycle, do you mean the same as induced cycle? $\endgroup$ Feb 12, 2014 at 0:25
  • $\begingroup$ I see there's already an answer here, which is great. However, our policy is not to allow simultaneous cross posting (you can cross post after a day or two if you're not getting the answer you want). $\endgroup$ Feb 12, 2014 at 0:54
  • $\begingroup$ Apologies, I won't do it again -- thanks for filling me in. $\endgroup$
    – GMB
    Feb 12, 2014 at 4:07

1 Answer 1


If $k$ is divisible by 2 we can take a clique on $n/2$ vertices and subdivide each edge once. This graph will have ${n/2 \choose k/2} \cdot (k/2-1)!/2$ cycles of length $k$.

Hence the total number of cycles is $\frac{1}{2} \sum_{i=k/2}^{i=n/2} {n/2 \choose i} \cdot (i-1)!$


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.