Given the down votes it attracted, it might have been better to motivate it with breeding dogs to avoid touching on taboos.° =)

But I enjoyed it from a mathematical perspective, since it's a a problem which can be perfectly described in graph theoretical terms: a directed graph with a "child of" relation with certain restrictions:

Here the solution in short, but hidden behind a spoiler tag to protect those interested.

°) apparently do most so called "purebred" dogs have an inbreeding factor of 25%. That's like the outcome of incest. One more reason why I'd always opt for a mongrel.

¹) in some western countries this is technically legal, because the laws don't cover that case.