<p>Let <span class="math-container">$N(n)$</span> be the number of triangles needed to cover <span class="math-container">$K_n$</span>.
Because every triangle covers only three of the <span class="math-container">$n\choose 2$</span> edges, we have <span class="math-container">$\frac{1}{3}{n\choose 2}\leq N(n)$</span> as a lower bound.</p>
<p>Note that the case <span class="math-container">$n=2$</span> is degenerate, as <span class="math-container">$K_2$</span> has only one edge and no triangles.
In the following analysis, I will allow myself to use triangles that cover only one edge (for <span class="math-container">$n&gt;2$</span>, this is without loss of generality because you can use an arbitrary third vertex to create a triangle).</p>
<p>To obtain an upper bound, we apply divide and conquer as follows.
For some <span class="math-container">$k+m=n$</span>, think of <span class="math-container">$K_n$</span> as the union of <span class="math-container">$K_m$</span>, <span class="math-container">$K_k$</span>, and <span class="math-container">$K_{k,m}$</span>.
In particular, let's pick <span class="math-container">$m:=\lfloor n/2\rfloor$</span> and <span class="math-container">$k:=\lceil n/2\rceil$</span>.
Label the vertices of <span class="math-container">$K_k$</span> by <span class="math-container">$u_0,\dots,u_{k-1}$</span> and the vertices of <span class="math-container">$K_m$</span> by <span class="math-container">$v_0,\dots,v_{m-1}$</span>.
For each edge <span class="math-container">$\{u_i,u_j\}$</span> of <span class="math-container">$K_k$</span>, place the triangle <span class="math-container">$\{u_i,u_j,v_{i+j\pmod m}\}$</span>.
This covers each edge of <span class="math-container">$K_k$</span> using <span class="math-container">$k\choose 2$</span> triangles, and also covers the edges <span class="math-container">$\{u_i,v_l\}$</span> of <span class="math-container">$K_{k,m}$</span> as long as <span class="math-container">$l\neq 2i\pmod m$</span>.
We can cover the remaining edges <span class="math-container">$\{u_i,v_{2i\pmod m}\}$</span> of <span class="math-container">$K_{k,m}$</span> using <span class="math-container">$k$</span> triangles.</p>
<p>Now, it remains to cover the edges of <span class="math-container">$K_m$</span>, which we do recursively.
This yields the upper bound <span class="math-container">$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$</span>.
For <span class="math-container">$n\leq 1$</span>, we have <span class="math-container">$N(n)=0$</span>, so we can write out the recurrence:
<span class="math-container">$$\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}$$</span></p>
<p>Therefore, the lower bound is tight up to a linear function of <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2021-02-18T22:49:32.097Z
2021-02-18T22:49:32.097Z
Tim
<p>If <span class="math-container">$n$</span> is congruent to <span class="math-container">$1$</span> or <span class="math-container">$3$</span> modulo <span class="math-container">$6$</span>, there is a covering of the complete graph <span class="math-container">$K_n$</span> with triangles so that each edge is used exactly in exactly one triangle, so this uses exactly <span class="math-container">$\frac{1}{3}\binom{n}{2}$</span> triangles. This is called a <em>Steiner triple system</em> and the answers to <a href="https://mathoverflow.net/questions/72084/constructing-steiner-triple-systems-algorithmically">this Math Overflow question</a>  give some ways to construct Steiner triple systems algorithmically</p>
<p>If <span class="math-container">$n$</span> is not congruent to <span class="math-container">$1$</span> or <span class="math-container">$3$</span> modulo <span class="math-container">$6$</span>, 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.</p>

CC BY-SA 4.0
2021-02-24T16:33:34.827Z
2021-02-24T16:33:34.827Z
Peter Shor 
<p>This problem is the subject of (and was completely solved in) the paper &quot;M. K. Fort Jr. and G. A. Hedlund. Minimal coverings of pairs by triples. Pacific Journal of Mathematics, 8(4):709–719, 1958.&quot;</p>
<p>In particular, the authors of that paper showed that the minimal number of triangles, for all <span class="math-container">$n$</span>, is given by</p>
<p><span class="math-container">$$\left\lceil \frac{n}{3} \left\lceil \frac{n-1}{2} \right\rceil \right\rceil.$$</span></p>
<p>This is of course equal to the <span class="math-container">$\frac{1}{3}\binom{n}{2}$</span> answer provided by Peter Shor's earlier answer if <span class="math-container">$n \equiv 1,3 \pmod{6}$</span>.</p>

CC BY-SA 4.0
2024-02-26T19:10:53.360Z
2024-02-26T19:10:53.360Z
Nathaniel Johnston
<p>Let <span class="math-container">$K_n$</span> be a complete graph, I am interested in knowing the minimum number of triangles required to get a edge cover of <span class="math-container">$K_n$</span>. 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 <span class="math-container">$n\choose 3$</span> i.e all possible triangles).</p>
<p>An example:</p>
<p>Let <span class="math-container">$K_4 = \{1,2,3,4\}$</span>, then any three of the following triangles make a full edge cover on <span class="math-container">$K_4$</span>:</p>
<p>{1,2,3}</p>
<p>{1,2,4}</p>
<p>{1,3,4}</p>
<p>{2,3,4}</p>
<hr />
<p>Furthermore, I would also like to add a generalisation i.e you assign a weight <span class="math-container">$w$</span> to each triangle such that <span class="math-container">$w \in [0,1] $</span>, now I want to have a cover that minimises the sum of <span class="math-container">$w$</span>, given that each edge's weight contribution sums to more than one.</p>
<p>What is the lower bound on this sum ?</p>

CC BY-SA 4.0
2021-02-18T16:10:42.193Z
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
CC BY-SA 4.0
2021-02-18T16:20:58.887Z
Thanks alot, I think your reasoning for the upper bound ( ${n \choose 2}$ ) is that the triangle cover is at-most as big as taking all edges to make the cover. But I am not able to follow the reasoning for the lower bound ?
SagarM
CC BY-SA 4.0
2021-02-18T16:27:44.703Z
Each triangle covers only 3 edges.
Emil Jeřábek
CC BY-SA 4.0
2021-02-18T16:31:27.747Z
Aaaah perfect thanks alot :D
SagarM
CC BY-SA 4.0
2021-02-18T16:35:58.377Z
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
CC BY-SA 4.0
2021-02-18T16:52:00.907Z
@EmilJeřábek , I would be more than willing to accept this if you were to post it as an answer.
SagarM
CC BY-SA 4.0
2021-02-18T17:09:20.247Z
Sorry, but if I may add a generalisation. How can this be to generalised to compute lower bound on fractional edge cover too i.e u can assign a weight between [0,1] to a triangle and the goal is to have minimal sum of u's such that the weight of each edge in this final contribution is atleast one
SagarM
CC BY-SA 4.0
2021-02-18T17:17:39.197Z
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
CC BY-SA 4.0
2021-02-18T18:32:53.873Z
The sequence is tabulated at http://oeis.org/A011975, which includes several relevant references and other information.
Emil Jeřábek
<graph-theory><covering-problems><vertex-cover>
Minimum number of triangles required to cover a complete graph?
SagarM
# Minimum number of triangles required to cover a complete graph?

(Asked by: username_0 on 2021-02-18)

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 ?

**Tags:** graph-theory, covering-problems, vertex-cover
> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks alot, I think your reasoning for the upper bound ( ${n \choose 2}$ ) is that the triangle cover is at-most as big as taking all edges to make the cover. But I am not able to follow the reasoning for the lower bound ?  
> **username_2**: Each triangle covers only 3 edges.  
> **username_0**: Aaaah perfect thanks alot :D  
> **username_2**: 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.  
> **username_0**: @EmilJeřábek , I would be more than willing to accept this if you were to post it as an answer.  
> **username_0**: Sorry, but if I may add a generalisation. How can this be to generalised to compute lower bound on fractional edge cover too i.e u can assign a weight between [0,1] to a triangle and the goal is to have minimal sum of u's such that the weight of each edge in this final contribution is atleast one  
> **username_2**: 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)$.  
> **username_2**: The sequence is tabulated at http://oeis.org/A011975, which includes several relevant references and other information.  

---

## 3 answers

### Answer by username_3 on 2021-02-18. Score: 4 | Accepted answer

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$.


---

### Answer by username_4 on 2021-02-24. Score: 5

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](https://mathoverflow.net/questions/72084/constructing-steiner-triple-systems-algorithmically) 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.


---

### Answer by username_5 on 2024-02-26. Score: 4

This problem is the subject of (and was completely solved in) the paper "M. K. Fort Jr. and G. A. Hedlund. Minimal coverings of pairs by triples. Pacific Journal of Mathematics, 8(4):709–719, 1958."

In particular, the authors of that paper showed that the minimal number of triangles, for all $n$, is given by

$$\left\lceil \frac{n}{3} \left\lceil \frac{n-1}{2} \right\rceil \right\rceil.$$

This is of course equal to the $\frac{1}{3}\binom{n}{2}$ answer provided by Peter Shor's earlier answer if $n \equiv 1,3 \pmod{6}$.


---

