Non-monochromatic triangles in a 2-edge-coloured graph (Q2001990): Difference between revisions

Summary: Let \(G = (V,E)\) be a simple graph and let \(\{R,B\}\) be a partition of \(E\). We prove that whenever \(|E| + \text{min}\{ |R|, |B| \} > \binom{|V|}{2}\), there exists a subgraph of \(G\) isomorphic to \(K_3\) which contains edges from both \(R\) and \(B\). If instead equality holds, and $G$ has no such subgraph, then we show that \(G\) is in one of a few simple classes.