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.



Cover a graph with small size complete graphs
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})$.


