Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 11 / 1 / ii / Solution

At any vertex, each complete bipartite graph $K_{k,k}$ containing it contributes exactly $k$ incident edges. Since the copies partition all incident edges of the complete graph, $n-1$ is a multiple of $k$. In particular $\gcd (n,k)=1$.

If there are $b$ copies, counting their edges givesThus $k^2\mid n(n-1)$. Since $n$ is coprime to $k^2$, it can be cancelled in this divisibility, yieldingIf $n=1$, the empty partition is consistent with the same conclusion, since every positive integer divides zero.