Cycles in the complete graph
Task number: 4199
Determine how many different cycles (all possible lengths) the complete \( K_n \) graph contains. Express the result using a sum.
Solution
Let \( k \in \{3, \dots, n \} \) be the length of the cycle. We select the vertices of the loop - this can be done in \( \binom{n}{k} \) ways. We choose one vertex arbitrarily, its successors form a permutation on \( k-1 \) vertices. The same cycle can be traversed in two directions, so it is counted twice.
Answer
The number of cycles is \( \sum\limits_{k=3}^n \binom{n}{k} \frac{(k-1)!}2 \).
