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:

edges.

Now in the n-k vertices we have extra edges in each of the m - 1 parts

Remove edges.

Add in the last part. Each of its k vertices needs to connect to all n - k other vertices.

Add .

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.