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

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.

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.

• It seems to me that just to get a single number placed in the matrix uses up four rows and four columns, with one diagonal missing (such diagonals can be at either angle, and "wrap around" mod 4). So I couldn't seem to get more than nine numbers in, and after that the remaining parts seemed not to be arrangable so as to place even the tenth number. Jul 10 '14 at 6:37
• Maybe. But the same argument works for $K_{6,6}$ and $K_{3,3}-I$, but my computer found an example in this case: $$\begin{array}{|cccccc|} \hline 1 & 1 & 2 & 2 & 3 & 3 \\ 1 & 3 & 1 & 4 & 4 & 3 \\ 4 & 1 & 1 & 2 & 4 & 2 \\ 4 & 5 & 5 & 4 & 6 & 6 \\ 5 & 3 & 5 & 6 & 3 & 6 \\ 5 & 5 & 2 & 6 & 6 & 2 \\ \hline \end{array}.$$ Jul 10 '14 at 6:43
• Interesting example. Only three of the four subsquares are of the "missing diagonal" type. The upper left has all the 4,3,2 missed from the other squares using up the 1,5,6. Maybe a construction like that could work for the 12x12... Jul 10 '14 at 10:21
• I meant the upper right above... Jul 10 '14 at 10:46
• Rebecca: I think I found a 12 by 12 matrix with the properties of the alternate way to view the problem. (See answer below.) It took a while to get the lower right 4 by 4 block to work out with the rest. Jul 10 '14 at 23:24

[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:

• Wow that's really nice!!! Thanks for that. (PS. I can't see the uploaded pictures from my location; hopefully I attached the right pics and they look decent.) Jul 11 '14 at 2:36
• @Rebecca -- Yes the colored version looks neat (from my viewing site anyway)! Jul 11 '14 at 3:31
• I believe this construction generalizes to give: $K_{12k^2,12k^2}$ decomposes into $K_{4k,4k}-kI$ for all $k \geq 1$. This is the $k=1$ case. (More formally, there exists $k$ disjoint $1$-factors of $K_{4k,4k}$ such that if we delete them to form graph $G$, then $K_{12k^2,12k^2}$ decomposes into $G$ subgraphs.) Fascinating. Jul 11 '14 at 6:14

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}$$