# A 2-coloring induces a monochromatic triangle

Let $$G$$ be a graph on $$5n$$ vertices and $$10n^2+1$$ edges. Each edge is coloured in red or blue. Prove that there is a monochromatic triangle.

Can we perhaps prove this by avoiding a probabilistic approach? I was thinking of using e.g. that a graph on $$v$$ vertices and $$e$$ edges must contain at least $$\frac{e}{3v}(4e-v^2)$$ triangles, but no idea if the info from this can be used altogether with a Pigeonhole argument or something else reasonably simple.

Any help appreciated!

(Source: Problems from the book, but no original source from there.)

We shall show that $$G$$ has a $$6$$-clique and we are done since any edge $$2$$-coloring of a complete graph on $$6$$ vertices induces a monochromatic triangle (for a proof, see here). Recall that Turán's theorem states that a $$K_{r+1}$$-free graph with $$n$$ vertices has at most $$t(n,r)$$ edges and that $$t(n,r) \leq \frac{(r-1)n^2}{2r}$$ so it suffices to show that $$e(G)> t(5n, 5)$$. But $$t(5n, 5) \leq \frac{4\cdot 25n^2}{10}=10n^2 < e(G)$$ and we are done.