2
$\begingroup$

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 2

2

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

  • 0
    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).2012-05-22
1

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

<span class=(13,4,1)-BIBD">

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.