Following on from this question:

Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

or equivalently

Q: Does there exist a $15 \times 15$ matrix containing $15$ copies of each symbol in $\{1,2,\ldots,15\}$ such that each row and each column containing a copy of symbol $i$ contains exactly $3$ copies of $i$?

The usual checks hold (a) the number edges in $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ is $5^2-10=15$ which divides $15^2$, the number of edges in $K_{15,15}$, and (b) the degrees of the vertices in $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ are $3$ which divides $15$, the degrees of the vertices in $K_{15,15}$.

The answers to the earlier question do not seem usable here.

I managed to fit $10$ in with the computer, but the computer seems woefully inadequate at solving this problem:

$10$ subgraphs in a $K_{15,15}$


1 Answer 1


Answering my own question: it is possible (see below). How I found it: I just started filling in the matrix by hand until I became better at avoiding "painting myself in the corner".

A decomposition

Unfortunately, this process was not too intelligent, so there's no hope of generalizing it. I'd still be happy to see a better method (if possible).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.