Bound the number of red edges in a red-blue coloring of $K_{n}$ such that no two red triangles share an edge Denote by $K_n$ the complete graph with $n$ vertices. Let $RE(n)$ be maximum number of red edges in a red-blue coloring of $K_{n}$ such that no two red triangles share an edge. I want to show that $RE(n)=o(n^2)$, or preferably the stronger result that I suspect: $RE(n)\leq O(n^{3/2})$.
The original problem: Show that in any red-blue coloring of $K_n$ such that no two red triangles share an edge, there exists a $K_{\lfloor\sqrt{2n}\rfloor}$ containing no red-triangles. I reduced this problem to the problem above.
 A: It's an interesting task.
Here we formulate a monochromatic version of this problem equivalent to the color one.

Theorem. If $G$ is a graph of order $n$ in which each edge enters at most one triangle,  then $G$ contains an induced triangle-free
subgraph of order at least $\sqrt{2n}$.

Here is a brief proof of this theorem.
Denote $q=[\sqrt{2n}]$ and assume that $n\geq3$.
We will say that a subset of vertices $S\subset V(G)$ has no triangles if $G[S]$ is an induced triangle-free subgraph.
We must find a subset without triangles containing $\geq q$ vertices.

*

*Let the graph $G$ have a vertex $v$ such that $\deg(v)=q-1$.

Let $N_G(v)$ be all neighbors of $v$ and $u\notin N_G(v)\cup\{v\}$ (at $n\geq3$ we have $q<n$).
The subset $N_G(v)\cup\{u\}$ has no triangles and $|N_G(v)\cup\{u\}|=q$.


*Let $\deg(v)\leq q-2$ for each vertex $v\in V(G)$.

Now let $S\subset V(G)$ be a maximal subset without triangles and $|S|=s$.
Since $\deg(x)\leq q-2$ for each vertex $x\in S$, the number of edges of the graph $H=G[S]$ is at most $s(q-2)/2$.
Because each edge enters at most one triangle we have
$$
|T|\leq|E(H)|\leq s(q-2)/2. 
$$
If $|S|+|T|<n$, then there exists a vertex $v\in V(G)$ and $v\notin S\cup T$
and the set $S\cup\{v\}$ has no triangles. This contradicts the maximality of $S$.
Thus $|S|+|T|\geq n$. So
$$
n\leq|S|+|T|\leq s+s(q-2)/2=sq/2\ \Rightarrow\ s\geq2n/q\geq\sqrt{2n}.
$$
This is what we needed to prove.
