Prove that in every coloration of the following graph, there exists one red or/and one yellow triangle.

Question

We have the following graph:

whose every line is colored either red or green.

Prove that in every possible coloration there exists one red or/and one green triangle.

This problem was introduced in reference to the Dirichlet's box principle.

Answer 1

I have a simple proof, although I am not sure if it is what you are looking for.

Consider this sub-graph

Instead of colours, I have used numbers. The three edges are coloured $1$. To avoid having a triangle, with all its edges coloured the same, we should colour $BD$, $BC$ and $CD$ with color $2$. Then, it is easily seen that the triangle $BCD$ makes a triangle of all edges coloured $2$, as in the next picture.

If there is such an structure in the coloured graph, then we definitely have a triangle of one colour. Now, just consider one of the vertices of the main graph and the edges connected to it. There are exactly $5$ edges, incident to the vertex and they are either coloured $1$ or $2$. According to pigeon-hole principle, there are at least $3$ of the $5$ edges, that are coloured the same. Those edges are exactly what we need to use the described structure, to show that there is a uni-coloured triangle.