[psyang]

Originally Posted by psyang

I hope these have been fun problems. I've had several in my head from when I first heard them, but I'm starting to look around for more - hopefully I can keep finding interesting ones to solve that don't require lots of background knowledge. Again, if anyone else has any to share, please do.

Here's a new problem. Let's see if it gets solved before the weekend is over or not.

You have a complete graph on 6 vertices (graph where all vertices are connected to each other) like below


Each edge can be colored either red or blue.

Show that regardless of the coloring, you can always find 3 edges that form a triangle that will have its edges all the same color.

No takers on this one?

The proof is pretty (imho):

Spoiler!

1. Pick any vertex. We'll choose vertex 1 in the diagram.
2. Vertex 1 has five attached edges. Because we are coloring the edges either red or black, we are guaranteed to have at least 3 colors the same color.
3. Each edge is identical to every other edge, so without loss of generality, we can say that edge 1-3, 1-4, and 1-5 are red.
4. If 3-5 is red, we are done (triangle 1-3-5 is red)
5. If 3-4 is red, we are done (triangle 1-3-4 is red)
6. If 4-5 is red, we are done (triangle 1-4-5 is red)
7. If 3-5, 3-4, and 4-5 are not red, then they must all be blue. But that means triangle 3-4-5 is blue and we are done.