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 \).

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email