How many cycles are possible in an unlabeled complete graph?

Question

I have found that the number of cycles for an unlabeled graph is ${n\choose m}\frac{(n-1)!}{2}$. n: Number of vertices in the graph m: The length of the cycle we need to determine.

Answer 1

This is not quite right, the correct answer (as you an check on OEIS) is that in the complete graph $K_n$, the number of cycles of length $k$ ($3\leq k \leq n$) is:

$$\binom{n}{k}\cdot \frac{(k-1)!}{2}$$

Here's a derivation:

• First, we need to pick a vertex set for our $k$-cycle. There are $\binom{n}{k}$ ways to choose a $k$-set from the vertex set of $K_n$.
• Having chosen $k$ vertices for the cycle, we need to find the order in which the cycle traverses those vertices. There are $k!$ ways to order the $k$ vertices, so we have a total of $\binom{n}{k}\cdot k!$ orderings.
• Not every ordering uniquely determines a cycle. Each cycle can be represented by exactly $2k$ different orderings, since we can pick one of $k$ starting vertices for the cycle, and one of $2$ directions to go around the cycle, to obtain an ordering for it. So we must divide by $2k$ to obtain $\binom{n}{k}\cdot \frac{(k-1)!}{2}$ cycles of length $k$.