# 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 complete bipartite graph $K_{n/2,n/2}$ (if $n$ is even) and $K_{(n-1)/2,(n+1)/2}$ (if $n$ is odd) have respectively $n^2/4$ edges and $(n^2-1)/4$ edges. So the number of edges in such graph is $O(n^2)$. There are no triangles in such a graph, hence there are no edges that are included of two triangles. Thus it seems that your statement is wrong. Jun 6, 2022 at 14:22
• I see and I agree with you. My reduction of the original problem turned it into an false statement, and the original problem holds because of some uneven distributions of red triangles in the $K_k$'s. Thank you for pointing out!
– Void
Jun 6, 2022 at 14:43
• It can be proved that the number of edges of a graph in which each edge enters no more than one triangle does not exceed $n^2/4$ as for a graph without triangles. Jun 7, 2022 at 17:31

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.

1. 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). The subset $$N_G(v)\cup\{u\}$$ has no triangles and $$|N_G(v)\cup\{u\}|=q$$.

1. 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|, 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.

• This is really clear. Thank you!
– Void
Jun 9, 2022 at 11:30

This problem can be solved by result of this problem. If you let {$$A_i$$} be the family of triangle vertex sets of $$G$$, you'll find this two problems are same.

https://artofproblemsolving.com/community/c6h48298p305430

It was problem from Romanian IMO team selection test, 1999.

• While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review Oct 19 at 2:58

The answer to the title question is that $$\operatorname{RE}(3)=3$$ and $$\operatorname{RE}(n)=\lfloor n^2/4\rfloor$$ for $$n\ne3$$.

To save typing let $$f(n)=\operatorname{RE}(n)$$. It is easy to verify that $$f(3)=3$$ and $$f(n)=\lfloor n^2/4\rfloor$$ for $$n=1,2,4$$. Moreover, it's easy to see that $$f(n)\ge\lfloor n^2/4\rfloor$$ for all $$n$$; just color the edges of $$K_n$$ so that the spanning subgraph formed by the red edges is a complete bipartite graph $$K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$$. We will prove by induction that $$f(n)\le\lfloor n^2/4\rfloor$$ for $$n\gt4$$.

First, by counting in two ways the pairs $$(e,v)$$ consisting of a red edge $$e$$ and a vertex $$v$$ not incident with $$e$$, we see that $$f(n)\cdot(n-2)\le nf(n-1)$$, i.e., $$f(n)\le\left\lfloor\frac n{n-2}f(n-1)\right\rfloor$$ for $$n\gt2$$.

For the inductive step, let $$n\gt4$$ and assume that $$f(n-1)\le\lfloor(n-1)^2/4\rfloor$$; we have to show that $$f(n)\le\lfloor n^2/4\rfloor$$. We consider two cases depending on the parity of $$n$$.

Case 1. $$n=2k$$ and $$f(n-1)=f(2k-1)\le\lfloor(2k-1)^2/4\rfloor=k(k-1)$$. Then $$f(n)=f(2k)\le\frac{2k}{2k-2}k(k-1)=k^2=\left\lfloor\frac{n^2}4\right\rfloor.$$ Case 2. $$n=2k+1$$ and $$f(n-1)=f(2k)\le\lfloor(2k)^2/4\rfloor=k^2$$. Then $$f(n)=f(2k+1)\le\left\lfloor\frac{2k+1}{2k-1}k^2\right\rfloor\le k^2+k=\left\lfloor\frac{n^2}4\right\rfloor$$ since $$\frac{2k+1}{2k-1}k^2\lt k^2+k+1.$$