# Ramsey's Theorem

*Ramsey's Theorem* in its simplest form (that is known as the *Friendship Theorem*) asserts that if the _{6} on six points are colored using two colors, there will be a *monochromatic triangle* (a K_{3} subgraph of K_{6} with all three edges having the same color.) More generally, Ramsey's theorem claims the existence of the Ramsey numbers R_{m}.

In a recent article, S. Golomb reports a result obtained by his student Herbert Taylor. As was observed by H. Taylor, the complete graphs on the number of points given by the Ramsey numbers R_{m} provide a sharp bound. (R_{m} is the smallest positive integer N such that, if a complete graph K_{N} on N points has all its

### Theorem

For every m ≥ 2, when a single edge is removed from the complete graph on R_{m} points, what remains can be colored with m colors without forming a monochromatic triangle.

### Proof

Let's for convenience N = R_{m}. Then, by the definition of R_{m}, the edges of K_{N-1} can be colored with m colors without generating a monochromatic triangle. Consider any such coloring. Pick any of the _{N-1} and denote it P. Add an N^{th} point P' that will serve as P's clone in the following sense: P' is to be connected to all the points Q of K_{N-1}, except P, and the new edges P'Q are to bear the color of PQ. Thus constructed graph has two properties:

- This is practically K
_{N}with only one edge (PP') missing. - It does not have a monochromatic triangle.

The first property is obvious. The second is almost so. If there is a monochromatic triangle P'Q_{1}Q_{2}, triangle PQ_{1}Q_{2} is also monochromatic which is impossible due to our selection of the coloring.

**Question**: Missing (unproven and not mentioned by Golomb) is an assertion that any color selection for PP' leads to a monochromatic triangle. Something to think about.

As an example, there is a K_{5} coloring and its expansion to K_{6} less one edge that do not contain monochromatic triangles (node 6 clones node 1):

### References

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

61152943 |