Blue-Empty Graph
I was going to post this puzzle tomorrow but I realized that leaving the inquisitive readers with just a solution to Langford’s problem would be very ill mannered. So here we go again! This one, like many others I will write about, comes from the late Martin Gardner’s prolific work as a puzzle writer:
Six Hollywood stars form a social group that has very special characteristics. Every two stars in the group either mutually love each other or mutually hate each other. There is no set of three individuals who mutually love one another. Prove that there is at least one set of three individuals who mutually hate each other. The problem leads into a fascinating field of graph theory, “blue-empty chromatic graphs”, the nature of which will be explained when the answer is given….on Wednesday, 12/29/2010.
Until then, enjoy the love triangle!
prathap sridharan
Every node is connected to 5 others. If you assume each edge is one of 2 colors. Then of the 5 edges, 3 must have the same color.
Consider a random node, say node 1. Take the 3 edges of the same color coming from this node. Let’s say they are connected to nodes 2, 3 and 4. Now, you cannot have the edges 2-3, 2-4 and 3-4 to have the same color. So, they must be a different color. And since there are only 2 colors, these 3 edges are of the same color, forming a triangle of the same color.
QED.
Karthik
January 3, 2011 at 2:07 am