Suppose we have a complete graph $G$ of size $n$. What is the minimum number of complete graph of size $k, k<n$ needed to cover all edges of the graph $G$? Are there any results related to this problem?



Cover a complete graph by smaller complete graphs
An equivalent reformulation of this question: if you can cover $K\_n$ by $m$ cliques, what is the smallest possible size of the largest clique? For example, if $K\_n$ is covered by $4$ cliques, then at least one of them has size $\frac{3n}{5}$ (which is rather surprizing, because the edge count yields a lower bound $\frac{n}{2}$). Also this $\frac{3n}{5}$ is asymptotically sharp: construct an example for $n=5$ and make multiple copies of each vertex.


The finite projective planes, as Brendan points out in his comment, can be used as follows. Vertices of the graph are points in the plane, and cliques are spanned by all points on a line. Since every pair of points lie on a unique line, every edge is covered exactly once. For a projective plane of order $k$ this gives a covering of $K\_{k^2+k+1}$ by $k^2 + k + 1$ cliques of size $k+1$. Vertex multiplication gives a covering of $K\_n$ by $k^2 + k + 1$ cliques of size $\frac{k+1}{k^2+k+1} n$ asymptotically. There are examples of finite projective planes for all $k$ equal to a prime power.


The most relevant reference, I think, is   

*P. Horák and N. Sauer, Covering complete graphs by cliques, Ars Combin. 33 (1992), 279–288.*   

They study several small values of $m$ that are not cardinalities of finite projective planes and find an exact estimate for the size of the largest clique. These estimates are always rational multiples of $n$ because they can be found by considering all possible Venn diagrams of the vertex sets of cliques.


By the way, here is a funny reformulation of the result stated in the first paragraph: Assume each person in a country speaks some of $4$ languages, and any two persons can communicate. Then there is a language spoken by at least $\frac{3}{5}$ of the population.


