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.)
Best Answer
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.