Ramsey's theorem

Question

I'm reading introduction to combinatorics and encountered an exercise I couldn't answer

Let S be a set of six points in the plane, with no three of the points collinear. Color either red or blue each of the 15 line segments determined by the points of S. Show that there is at least two triangles determined by points of S which are either a red triangle or a blue triangle.(Both may be red, or both may be blue and one may be red the other bule)

Thanks if you can give me any help.

Answer 1

To the modified version of your question: we can always find a second triangle, but not a third. The proof is as follows:

We start by acknowledging the first triangle (let's say that it's red), as guaranteed from the previous proof. Choose a point not in that triangle. Following the steps of the original proof, either we have a new triangle, or there are three blue edges from this point to each point on the red triangle.

Now look at the three points outside of the red triangle, supposing that each has three blue edges from each point on the red triangle. If any two of these outside points are connected with a blue edge, we have a blue triangle. Otherwise, the outside points form another red triangle. Either way, we have found a second triangle.

To disprove the guaranteed existence of a third triangle, consider the graph in which these edges are blue and the rest are red. We have two red triangles, but no more.

Answer 2

Hint: consider any point on the graph. This point has $5$ protruding line segments, each of which are red or blue. We note that there must be at least $3$ line segments of the same color.

We can show that the points on the end of these $3$ segments form a red or a blue triangle. How?

Hint: Suppose that the three segments we found were red. Let's look at the points on the end of those segments, and the connection from each to the other. If any two are connected with a red line, then we have a red triangle. Draw this to check.

Now, what if none of the two points at the end of these $3$ segments are connected with a red line? Can we say anything about either a red or blue triangle?

Some helpful pictures: We looked at a point $A$, and noticed that whatever colors come out of $A$, we have to have $3$ that are the same

We then looked at the three points on the end. If there's a red line between any $2$ of them, then we have a red triangle. What happens if there isn't?

ANSWER:

There must be a blue triangle

Answer 3

This is really a graph theory problem, so there is no need to worry about planar embeddings or collinearity. What you mean is that any 2-coloring of the edges in $K_6$ (complete graph on six vertices) contains a monochromatic triangle.

The classic proof of this is as follows: pick some vertex $v$. There are five vertices connected to it, so three of these edges will have the same color (say, red). The three corresponding vertices will form a monochromatic triangle (why?).

The moral of this exercise is essentially to see how to apply the pigeonhole principle. Whenever you've got only two colors and a lot of edges, look for large collections of monochromatic edges. This is a common theme of Ramsey theory on finite graphs.

Here is another exercise with a similar solution: show that if you 2-color the planar lattice $\mathbb{N}^2$, you must have a monochromatic rectangle. Edit: 2-color the vertices of the lattice, I mean.

Edit: I have removed a crucial step in my proof, since Omnomnomnom has given a very good hint along the lines of "figure out the missing step".