# Cover a complete graph by smaller complete graphs

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?

• Buzzwords "clique cover", "content decomposition", "covering number". Tons of variations. Some cases are very difficult, for example the question of whether $K_n$ can be exactly covered (no edge covered twice) by copies of $K_k$ for fixed $3\le k\le n$ is equivalent to the existence of projective planes of order $k$. – Brendan McKay Nov 6 '16 at 0:00
• Note that I got the details wrong. See Ivan's answer for the correct version. – Brendan McKay Nov 6 '16 at 9:04

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