# Bounding number of k-cycles in a graph

Fix any $$k \geq 3$$, and suppose I have a simple undirected graph $$G=(V,E)$$. I want a bound on the number of $$k$$ cycles in $$G$$ as a function of $$|E|$$. In particular, I would like to prove the following "conjectured" statement:

W.T.S: Given any $$G=(V,E)$$, the number of $$k$$-cycles in $$G$$ is at most $$O(|E|^{k/2})$$.

Clearly $$\binom{|V|}{k}$$ is tight if we only wanted a bound in terms of $$|V|$$, which comes from the complete graph on $$|V|$$ vertices. However, it is not as clear how to prove a tight upper bound in terms of $$|E|$$. The intuition for the conjecture is that, up to a constant, it seems that it should be optimal to arrange your edges in a complete graph (if $$k$$ is even, you do win a constant by taking a complete bipartite graph instead of a complete graph).

There seem to be a few proofs of this fact for triangles (k=3), for instance https://math.stackexchange.com/questions/823481/number-of-triangles-in-a-graph-based-on-number-of-edges. However, they don't generalize in any clear way to larger $$k$$. Moreover, I don't know of any k-cycle enumeration algorithms for k>3 that are parameterized by $$|E|$$ (the runtime of which would provide an upper bound).

For my application I actually only need bounds for odd $$k$$, but it seems that any such proof should generalize to any $$k$$. Also, to be clear, I'm only interested in asymtotic bounds here in terms of $$|E|$$ (getting tight constants seem much more difficult). Any suggestions or references that I missed would be much appreciated.

• For $k=4$ the appropriate complete graph has nearly twice as many $k$-cycles as the complete bipartite graph, not that that changes things. For example $K_{50}$ and $K_{35,35}$ and each have $|E|=1225$ but the first has $690900$ $4$-cycles and the latter has $354025.$ The same should be true for larger ever $k$ as well. – Aaron Meyerowitz Jan 30 at 4:59
• Ooops, right you are. I miscounted the number of 4 cycles in the complete graph, I forgot that four vertices give rise to multiple 4-cycles. Thanks for catching this! – Rajesh Jayaram Jan 31 at 17:48