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.

cliqueis non-standard. I suggest changing the title to something like covering the edges of a graph with small subgraphs. $\endgroup$