Number of triangles in $K_n$ that don't share any edges Consider $K_n$ the complete graph with n vertices, $n\ge3$.
Prove that there is a set $S$, of triangles from $K_n$ such that there are not $2$ triangles from $S$ that share an edge and $|S|\ge\frac{(n-2)(n-1)}{6}$.
By triangle I simply mean a triplet $(a,b,c)$ of vertices from $K_n$ and the edges $ab,bc$ and $ca$. In other words, a $K_3$.
My work:
At first glance I tought that I could solve this by finding a specific graph, for example:
We take the triangle $(i,j,k)$ if and only if $i,j$ and $k$ satisfy some weird condition but this seems very unlikely to solve the problem because for small cases the way in which we have to choose the triangles seems very "random".
My most promising idea is induction on $n$ but we encounter a lot of problems here as well. The main problem is that in some weird cases, when we add the next vertex we will only be able to add $1$ more triangle and for big enough $n$ this is not enough.
However I think that induction has a lot of potential in this problem but is has to be a lot stronger than just the statement of the problem.
 A: Hint
Note that$$\frac{(n-1)(n-2)}6=\frac1n\binom{n}3$$ This suggests that you can get the requisite number of triangles by taking all $\binom n3$ triangles, dividing them into $n$ equal groups, and taking of the triangles in one of the groups. There are some cases where $\binom{n}3$ is not divisible by $n$, but don't worry about that yet.
The question is, how to you group all of the triangles into $n$ groups? This is like taking all of the triangles $\{a,b,c\}$ and assigning them a number between $1$ and $n$. The numbers $a,b$ and $c$ are also between $1$ and $n$. What kind of operation can you do that will take three numbers between $1$ and $n$ and return a number between $1$ and $n$?
A: See Theorem 2 in Feder, Tomás, and Carlos S. Subi. "Packing Edge-Disjoint Triangles in Given Graphs." Electron. Colloquium Comput. Complex. Vol. 19. 2012, which implies that the largest $S$ satisfies $|S| = \binom{n}{2}/3$ if $n \equiv 1,3 \pmod 6$ and otherwise $|S| < \binom{n}{2}/3$.  Note that your target is $\binom{n-1}{2}/3$.
