Cycles in complete bipartite graph

Task number: 4198

Show that the number of cycles in the complete bipartite graph \( K_{n, n} \) is \( \displaystyle \sum_{k = 2}^ n \binom{n}{k}^2 \frac{k! (k-1)!}{2} \).

  • Solution

    The term \(\binom{n}{k} \) corresponds to the selection of vertices from one part. It is in the square root because we choose independently from both parts.

    If we choose one vertex arbitrarily, its successors from the same part form a permutation on \( k-1 \) vertices, while from the other on \( k \) vertices. The same cycle can be traversed in two directions, so it is counted twice.

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