<p>After some search, I have found out that a solution was already published in 1948. De Bruijn and Erdos proved that it is <strong>not</strong> possible to partition the edges of $K_n$ into fewer than $n$ smaller cliques. I do not have a direct link to their paper, but it is referred to in the 1988 paper by <a href="http://bsmath.hu/~p_erdos/1988-04.pdf" rel="nofollow">Erdos, Faudree and Ordman, "Clique Partitions and Clique Coverings"</a>.</p>

CC BY-SA 3.0
2015-05-25T03:49:37.480Z
The 1948 paper is [here](http://alexandria.tue.nl/repository/freearticles/597479.pdf).
Austin Buchanan
CC BY-SA 3.0
2015-05-25T03:47:11.270Z
2015-05-25T03:47:11.270Z
Andras Farago
<p>Consider the (simple, undirected) complete graph $K_n$. Is it possible to partition its edges into less than $n$ cliques, each having less than $n$ vertices?</p>

<p><strong>Note:</strong> It is easy to see that $n$ cliques of size $&lt;n$ always suffice. Take a $K_{n-1}$ as one clique, and take a $K_2$ for each of the $n-1$ edges that are not contained in the $K_{n-1}$. This gives an edge partition into $n$ cliques, each with size $&lt;n$. The question is whether there is such a partition into <strong>less</strong> than $n$ cliques of size $&lt;n$.</p>

<graph-theory>
Partitioning the edges of a complete graph into smaller complete graphs
Andras Farago
# Partitioning the edges of a complete graph into smaller complete graphs

(Asked by: username_0 on 2015-05-25)

Consider the (simple, undirected) complete graph $K\_n$. Is it possible to partition its edges into less than $n$ cliques, each having less than $n$ vertices?

**Note:** It is easy to see that $n$ cliques of size $less than $n$ cliques of size $

**Tags:** graph-theory

---

## 1 answers

### Answer by username_0 on 2015-05-25. Score: 4 | Accepted answer

After some search, I have found out that a solution was already published in 1948. De Bruijn and Erdos proved that it is **not** possible to partition the edges of $K\_n$ into fewer than $n$ smaller cliques. I do not have a direct link to their paper, but it is referred to in the 1988 paper by [Erdos, Faudree and Ordman, "Clique Partitions and Clique Coverings"](http://bsmath.hu/~p_erdos/1988-04.pdf).

> **Comments:**
> **username_1**: The 1948 paper is [here](http://alexandria.tue.nl/repository/freearticles/597479.pdf).  

---

