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.
