# 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 ?

• Note that this number is asymptotically $\Theta(n^2)$ because there is a trivial ${n \choose 2}$ bound of just covering at least a single new edge in each triangle, and any cover must contain at least $|E|/3 = {n \choose 2}/3$ edges. – user3209423940248 Feb 18 at 16:10
• Each triangle covers only 3 edges. – Emil Jeřábek Feb 18 at 16:27
• A better upper bound is $\lceil\frac12\binom n2\rceil$. If $n$ is odd, then $K_n$ is eulerian; fix an eulerian path, split it in $\frac12\binom n2$ pairs of neighbouring edges, and complete each pair to a triangle. For $n$ even, take a covering of $K_{n-1}$ as above, and use $n/2$ further triangles to cover edges incident to the $n$th vertex. – Emil Jeřábek Feb 18 at 16:35
• Well, these are simple observations, and perhaps someone can figure out the right multiplicative constant yet. Concerning fractional edge covers, this case is much simpler: the $\frac13\binom n2$ lower bound still applies, and now it is in fact the exact optimal value: just take every triangle with weight $1/(n-2)$. – Emil Jeřábek Feb 18 at 17:17
• The sequence is tabulated at oeis.org/A011975, which includes several relevant references and other information. – Emil Jeřábek Feb 18 at 18:32

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>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)&\leq \sum_{i=1}^{\log_2 n} \left[{\lceil n/2^i\rceil\choose 2} + \lceil n/2^i\rceil\right]\\ &\leq \sum_{i=1}^{\log_2 n} \left[{\frac{n}{2^i}+1\choose 2} + \frac{n}{2^i} + 1\right]\\ &= \sum_{i=1}^{\log_2 n} \left[\frac{1}{2}(\frac{n}{2^i})^2+\frac{3}{2}\frac{n}{2^i} + 1\right]\\ &= \frac{n^2-1}{6} + \frac{3(n-1)}{2} + \log_2 n\\ &= \frac{1}{3}{n\choose 2} + O(n). \end{align}

Therefore, the lower bound is tight up to a linear function of $$n$$.

If $$n$$ is congruent to $$1$$ or $$3$$ modulo $$6$$, there is a covering of the complete graph $$K_n$$ with triangles so that each edge is used exactly in exactly one triangle, so this uses exactly $$\frac{1}{3}\binom{n}{2}$$ triangles. This is called a Steiner triple system and the answers to this Math Overflow question give some ways to construct Steiner triple systems algorithmically

If $$n$$ is not congruent to $$1$$ or $$3$$ modulo $$6$$, then you can round it up so that it is, and get a good covering that way, although I believe combinatorists have found even better ones.