Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Question

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)?

The obvious necessary conditions work:

• $K_{12,12}$ has $12^2$ edges which is divisible by $12$, the number of edges in $K_{4,4}-I$.

• Vertices in $K_{12,12}$ have degree $12$ which is divisible by $3$, the degree of the vertices in $K_{4,4}-I$.

I haven't put too much effort into solving this thus far. It seems like it would require considerable effort to solve computationally, so I'm hoping there is a cleverer solution.

An alternative way of thinking about this problem:

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

This question is a specific instance of another problem I'm thinking about.

Answer 1

[Edit (by Rebecca): the second version was correct, but let me tidy things up a bit.]

$$ \begin{array}{|cccccccccccc|} \hline 5&1&1&1&9&2&2&2&5&5&9&9 \\ 1&5&1&1&2&9&2&2&5&5&9&9\\ 1&1&6&1&2&2&10&2&6&6&10&10\\ 1&1&1&6&2&2&2&10&6&6&10&10\\ 11&3&3&3&7&4&4&4&11&11&7&7\\ 3&11&3&3&4&7&4&4&11&11&7&7\\ 3&3&12&3&4&4&8&4&12&12&8&8\\ 3&3&3&12&4&4&4&8&12&12&8&8\\ 5&5&6&6&9&9&10&10&5&6&9&10\\ 5&5&6&6&9&9&10&10&6&5&10&9\\ 11&11&12&12&7&7&8&8&11&12&7&8\\ 11&11&12&12&7&7&8&8&12&11&8&7\\ \hline \end{array} $$

In color:

And here's an illustration of the decomposition:

Answer 2

Actually, there seems to be an easy construction that I overlooked when writing my question:

• $K_{6,6}$ decomposes into three $K_{4,4}-I$ subgraphs (illustrated below).
• We can combine four of these to decompose $K_{12,12}$ into $K_{4,4}-I$ subgraphs.

The non-edges happen to be at just the right spots for this to work:

Here's the matrix version:

$$ \begin{array}{|cccccc|} \hline 2 & 1 & 1 & 1 & 2 & 2 \\ 1 & 2 & 1 & 1 & 2 & 2 \\ 1 & 1 & 1 & 3 & 3 & 3 \\ 1 & 1 & 3 & 1 & 3 & 3 \\ 2 & 2 & 3 & 3 & 3 & 2 \\ 2 & 2 & 3 & 3 & 2 & 3 \\ \hline \end{array} \longrightarrow \begin{array}{|cccccc|cccccc|} \hline 2 & 1 & 1 & 1 & 2 & 2 & 8 & 7 & 7 & 7 & 8 & 8 \\ 1 & 2 & 1 & 1 & 2 & 2 & 7 & 8 & 7 & 7 & 8 & 8 \\ 1 & 1 & 1 & 3 & 3 & 3 & 7 & 7 & 7 & 9 & 9 & 9 \\ 1 & 1 & 3 & 1 & 3 & 3 & 7 & 7 & 9 & 7 & 9 & 9 \\ 2 & 2 & 3 & 3 & 3 & 2 & 8 & 8 & 9 & 9 & 9 & 8 \\ 2 & 2 & 3 & 3 & 2 & 3 & 8 & 8 & 9 & 9 & 8 & 9 \\ \hline 5 & 4 & 4 & 4 & 5 & 5 & 11 & 10 & 10 & 10 & 11 & 11 \\ 4 & 5 & 4 & 4 & 5 & 5 & 10 & 11 & 10 & 10 & 11 & 11 \\ 4 & 4 & 4 & 6 & 6 & 6 & 10 & 10 & 10 & 12 & 12 & 12 \\ 4 & 4 & 6 & 4 & 6 & 6 & 10 & 10 & 12 & 10 & 12 & 12 \\ 5 & 5 & 6 & 6 & 6 & 5 & 11 & 11 & 12 & 12 & 12 & 11 \\ 5 & 5 & 6 & 6 & 5 & 6 & 11 & 11 & 12 & 12 & 11 & 12 \\ \hline \end{array} $$