The complete graph with 6 points and 15 edges has each edge colored red or blue. Show that we can find 3 points such that the 3 edges joining them are the same color.
Solution
Take any point A. It has 5 edges, so at least 3 of them must be the same color. wlog it is red. So we have B, C, D with AB, AC, AD all red. Now if any of the three edges BC, CD, DB is red, then that gives us a red triangle. But if they are all blue, then BCD is a blue triangle.
© John Scholes
jscholes@kalva.demon.co.uk
5 Mar 2002