Here is the closest I get. It comes up with the formula, but not as directly as I had hoped.
Consider an . Take away one part. Create a complete graph with remaining n-k vertices:
Now in the n-k vertices we have extra edges in each of the m - 1 parts
Add in the last part. Each of its k vertices needs to connect to all n - k other vertices.
So we get .
If you simplify this you will get the formula (remember n = mk).
I would like to know if there is a more direct argument for the formula without the need for algebra.