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

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:

## 1 Answer

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".

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).