Minimum number of triangles required to cover a complete graph? Let $K_n$ be a complete graph, I am interested in knowing the minimum number of triangles required to get a edge cover of $K_n$. In case there is no closed-form solution to this problem, then I would like to know the best known upper bound (the naive bound is $n\choose 3$ i.e all possible triangles).
An example:
Let $K_4 = \{1,2,3,4\}$, then any three of the following triangles make a full edge cover on $K_4$:
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}

Furthermore, I would also like to add a generalisation i.e you assign a weight $w$ to each triangle such that $w \in [0,1] $, now I want to have a cover that minimises the sum of $w$, given that each edge's weight contribution sums to more than one.
What is the lower bound on this sum ?
Let $N(n)$ be the number of triangles needed to cover $K_n$.
Because every triangle covers only three of the $n\choose 2$ edges, we have $\frac{1}{3}{n\choose 2}\leq N(n)$ as a lower bound.
Note that the case $n=2$ is degenerate, as $K_2$ has only one edge and no triangles.
In the following analysis, I will allow myself to use triangles that cover only one edge (for $n&gt;2$, this is without loss of generality because you can use an arbitrary third vertex to create a triangle).
To obtain an upper bound, we apply divide and conquer as follows.
For some $k+m=n$, think of $K_n$ as the union of $K_m$, $K_k$, and $K_{k,m}$.
In particular, let's pick $m:=\lfloor n/2\rfloor$ and $k:=\lceil n/2\rceil$.
Label the vertices of $K_k$ by $u_0,\dots,u_{k-1}$ and the vertices of $K_m$ by $v_0,\dots,v_{m-1}$.
For each edge $\{u_i,u_j\}$ of $K_k$, place the triangle $\{u_i,u_j,v_{i+j\pmod m}\}$.
This covers each edge of $K_k$ using $k\choose 2$ triangles, and also covers the edges $\{u_i,v_l\}$ of $K_{k,m}$ as long as $l\neq 2i\pmod m$.
We can cover the remaining edges $\{u_i,v_{2i\pmod m}\}$ of $K_{k,m}$ using $k$ triangles.
Now, it remains to cover the edges of $K_m$, which we do recursively.
This yields the upper bound $N(n)\leq N(m)+{k\choose 2}+k\leq N(\lfloor n/2\rfloor)+{\lceil n/2\rceil\choose 2}+\lceil n/2\rceil$.
For $n\leq 1$, we have $N(n)=0$, so we can write out the recurrence:
$$\begin{align}N(n)&amp;\leq
\sum_{i=1}^{\log_2 n} \left[{\lceil n/2^i\rceil\choose 2} + \lceil n/2^i\rceil\right]\\
&amp;\leq
\sum_{i=1}^{\log_2 n} \left[{\frac{n}{2^i}+1\choose 2} + \frac{n}{2^i} + 1\right]\\
&amp;=
\sum_{i=1}^{\log_2 n} \left[\frac{1}{2}(\frac{n}{2^i})^2+\frac{3}{2}\frac{n}{2^i} + 1\right]\\
&amp;= \frac{n^2-1}{6} + \frac{3(n-1)}{2} + \log_2 n\\
&amp;= \frac{1}{3}{n\choose 2} + O(n).
\end{align}$$
Therefore, the lower bound is tight up to a linear function of $n$.