A Problem From The Sixth IMO (1964)

I am passing a very busy time because of my undergraduate thesis!

But still I managed to solve this really entertaining problem from the sixth IMO:

Problem Description:

Each of 17 students talked with every other student. They all talked about three different topics. Each pair of students talked about one topic. Prove that, there are three students that talked about the same topic among themselves.

An obvious way to restate the problem is:

Given a complete graph with 17 nodes. Each edge is colored with one of three colors. Prove that, there exists a triangle (i.e. cycle of length 3) such that, all three edges are colored with the same color.

Initially I had no idea how to attack the problem. I started drawing a complete graph with 17 nodes which turned out to be a jungle of edges! So, I had to simplify the problem somehow to make it more accessible. Now, what makes the problem hard ? Clearly, the size 17 is a bit too high to draw some graphs and try to understand what happens when we color the edges.

So, I came up with the following simpler problem, by solving which, I got the required insight to solve the original problem.

The Simpler Problem:

Given a complete graph with 6 nodes. Each edge is colored either red or blue. Prove that, there exists a triangle with all three edges colored with the same color.

Now, this problem is more accessible in a sense, because it is easier to draw a complete graph with 6 nodes and color the edges with 2 colors and try to understand what happens.

How did I come up with these numbers, 6 nodes, 2 colors ? Well, I drew a few complete graphs with 4 nodes, 5 nodes and then 6 nodes and found that, I could not color the 6-node-graph with 2 colors without creating a critical triangle (lets denote those single-colored-triangle by this name)

A Journey to the solution of "the simpler problem":

I kept experimenting with this smaller problem and the following observations emerged one by one:

1. If edge (a,b) and (a,c) are colored red then, edge (b,c) must be colored blue (if we want to avoid creating critical triangles)
2. if edge (a,b) and (a,c) are colored red and edge (c,d) and (b,d) are colored blue then, we are in a situation where critical triangle is unavoidable, whether we color the edge (b,c) red or blue.
3. if all of the edges (a,d), (b,d) and (c,d) are colored red, we cannot avoid a critical triangle, because, coloring any one of the edges (a,b), (b,c) or (c,a) with color red will create a red triangle and coloring all of them with color blue will create a blue triangle.

The last observation is the most important one! Because, it is easy to show that, this circumstance is unavoidable in case of 6 nodes and 2 colors. Why?

As the graph is a complete graph of 6 nodes, every node will have 5 edges adjacent to it. If we color those 5 edges with 2 colors, then by the pigeonhole principle, at least 3 edges will have the same color. And we are done, because this is the situation of the above image! The simpler problem is solved! And, this has provided us with an insight and a technique that will be directly useful in the solution of the actual problem.

So, here is the solution to the main problem:

Here, the complete graph has 17 nodes and we have 3 colors to color the edges. Any node u has 16 edges adjacent to it. By the pigeonhole principle, at least 6 of those edges will have the same color (say, red). denote the nodes on the other side of those edges to be v₁, v₂ ... v₆. Note that, we cannot color any of the edges-among-them red because, this will create a red triangle. So, the edges among v₁, v₂ ... v₆ must be colored with the other 2 colors! And Here We Are! This is exactly the smaller version of the problem (6 nodes, 2 colors) that we have solved earlier.
Note that, instead of describing the final solution formally in mathematical language, I have tried to describe the way I have attacked the problem. This is because, that is the real-fun-part of problem-solving!

An Easy Exercise:
Find the minimum number of nodes of a complete graph, for which there always exists a critical-triangle (defined earlier) if we color the edges with four colors.