Hello everyone interested. Here's a seemingly simple problem. Suppose $G$ is a complete, simple graph with vertices $\{1,2,..,n\}$, $n\geq k\geq 3$.
How many cycles of length $k$ can we have on $G$?
The statement seems simple but I have trouble putting everything together. So I say fix a vertex and start forming cycles with length k. But I get nowhere... What is the proper approach to this problem since counting is not easy? Is there a relevant theorem that I am unaware of?
Thanks for any help...
Because the graph $G$ is complete, a cycle of length $k$ with a specified starting point and direction is simply an ordered $k$-tuple of distinct vertices of $G$. There are $\frac{n!}{(n-k)!}$ such $k$-tuples, hence $\frac{1}{2k}\frac{n!}{(n-k)!}$ such cycles.