# Cover a graph with small size complete graphs

Given a complete graph with $$n$$ nodes, if we want to use $$n$$ complete subgraphs to cover the graph and ask what is the minimum possible size of each complete subgraph, the answer is $$\Theta(\sqrt{n})$$: there are $$\Theta(n^2)$$ edges and each clique can cover at most $$O(n)$$ edges, so the lower bound for the complete subgraph size is $$\Omega\left(\sqrt{\frac{n^2}{n}}\right)=\Omega\left(\sqrt{n}\right)$$. This lower bound is also tight: we can partition vertices into $$\sqrt{n}$$ sets with $$\sqrt{n}$$ nodes in each set, and any pair of sets form a complete subgraph.

I want to ask for a generalization of the above question when the graph is not a complete graph: when the graph has $$m$$ edges, is it always possible to cover the graph by $$n$$ cliques with size $$\sqrt{\frac{m}{n}}$$? (the clique can contain non-edge). To be precise, I want to find the smallest possible $$k(n,m)$$ such that for any graph $$G$$ with $$n$$ vertices and $$m$$ edges, there exists $$n$$ vertex sets $$S_1,S_2,...,S_n\subseteq V$$ each with size $$k(n,m)$$ and every edge $$(u,v)$$ has $$u,v$$ both contained in some $$S_i$$.

I searched for clique edge covering but most of the results only consider the case where cliques cannot cover non-edge. I wonder if there exists any similar research in the setting when cliques can cover non-edge.

• In the definition, don't you want $S_1,\ldots,s_\ell$ to be cliques? Jan 31 at 18:47
• $S_1,S_2,...,S_n$ are vertex sets. In the definition I want for any edge $(u,v)$ we have $u,v\in S_i$ for some $i\in[n]$. This is another way to say we want to use $n$ cliques to cover all the edges. Jan 31 at 19:03
• It seems that if G has a large girth, then coverings with small cliques will be inefficient (will contain many "non-edges"). Maybe this provides examples where $\sqrt{m/n}$ cliques are not enough? Jan 31 at 19:55
• The way you are using the term clique is non-standard. I suggest changing the title to something like covering the edges of a graph with small subgraphs. Feb 1 at 8:06

Here is an example showing that the clique size $$\sqrt{m/n}$$ does not suffice.
Graphs on $$n$$ vertices without 4-cycles have less than $$O(n^{3/2})$$ edges, and there is a series of examples where this asymptotic bound is attained. If one wishes to cover all edges of such a dense graph with $$n$$ cliques of equal size, then these cliques must contain $$\Theta(n^{1/2})$$ edges on average, and are still 4-cycle-free. Thus the clique size is at least $$n^{1/3}$$, while $$\sqrt{m/n} = \Theta(n^{1/4})$$.