# Graph decomposition

What is the smallest $n \in \mathbb{N}$ with $n \geq5$ such that the edge set of the complete graph $K_n$ can be partitioned (decomposed) to edge disjoint copies of $K_4$?

I got a necesary condition for the decomposition is that $12 |n(n-1)$ and $3|n-1$, thus it implies $n \geq 13$. But can $K_{13}$ indeed be decomposed into edge disjoint copies of $K_4$?

-

## 2 Answers

The degree of $K_9$ is 8, whereas the degree of $K_4$ is 3. Since $3$ does not divide $8$, there is no $K_4$ decomposition of $K_9$.

$K_n$ has a decomposition into edge-disjoint copies of $K_4$ whenever $n \equiv 1 \text{ or 4 } (\text{mod} 12)$, so the next smallest example after $K_4$ is $K_{13}$.

-
Now I see, a stronger condition would be 12 divides n(n-1) and 3 divides n-1, thus the smallest n is 13,but can you provide a decomposition of K13? – user31899 May 22 '12 at 7:00
From hal.inria.fr/docs/00/42/91/74/PDF/BC-ICC03.pdf: There is a decomposition of K13 into 13 subgraphs K4 (namely the subgraphs Bi = {i, i + 1, i + 4, i + 6} for i = 0, 1, . . . , 12, the numbers being taken modulo 13). – Wonder May 22 '12 at 7:09

Here's the $(13,4,1)$-BIBD from the designtheory.org database (here), where it is described as unique up to isomorphism.

To check it's indeed a $(13,4,1)$-BIBD, we can run the following code in GAP:

S:=
[ [   1,   2,   3,   4 ],
[   1,   5,   6,   7 ],
[   1,   8,   9,  10 ],
[   1,  11,  12,  13 ],
[   2,   5,   8,  11 ],
[   2,   6,   9,  12 ],
[   2,   7,  10,  13 ],
[   3,   5,   9,  13 ],
[   3,   6,  10,  11 ],
[   3,   7,   8,  12 ],
[   4,   5,  10,  12 ],
[   4,   6,   8,  13 ],
[   4,   7,   9,  11 ] ];

A:=[];
for P in S do
T:=Combinations(P,2);
A:=Concatenation(A,T);
od;
Size(A)=Binomial(13,2);


which returns true.

-