Finding isomorphic matchings of labelled cliques

Question

There are 2 complete graphs with n vertices each. Assuming that k vertices are coloured 'R' and (n-k) vertices are coloured 'B' for both graphs, how does one find out the number of isomorphic matchings between these two graphs?

Answer 1

I'm assuming that by color isomorphism you means every vertex maintain the same number of red (and blue) neighbors under the isomorphism.

If that is the case, every red(blue) vertex must be mapped to a red(blue) vertex, otherwise it will have one more red neighbor (and one less blue neighbor).

Since there are $k$ red vertices, there are $k!$ isomorphisms between the red vertices only. In the same way there are $(n-k)!$ isomorphisms between the blue vertices to themselves.

In total $(k!)\cdot(n-k)!$

Note that it is sufficient to look for isomorphism from one colored complete graph to it self.