3
$\begingroup$

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 $<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 $<n$. The question is whether there is such a partition into less than $n$ cliques of size $<n$.

$\endgroup$

1 Answer 1

4
$\begingroup$

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".

$\endgroup$
1
  • 2
    $\begingroup$ The 1948 paper is here. $\endgroup$ May 25, 2015 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.