Problem:
The chromatic number of the (infinite) plane, denoted by , is the smallest number of colors with which we can color the points on the plane in such a way that no two points of the same color are one unit apart.
Prove that .
Problem:
The chromatic number of the (infinite) plane, denoted by , is the smallest number of colors with which we can color the points on the plane in such a way that no two points of the same color are one unit apart.
Prove that .
Solution:
Suppose . Consider the following configuration, where each segment has unit length. Then the points , and must receive different colors, and so are the points , and . This will force points and to receive the same color as , which is a contradiction. Thus, we obtain .
On the other hand, we will exhibit a coloring of the points on the plane using 7 colors in such a way that points one unit apart have different colors. We first tile the plane by regular hexagons with unit sides. Now, we color one hexagon with color 1, and its six neighbors with colors , as highlighted in the following diagram.
The union of the seven highlighted hexagons forms a symmetric polygon of 18 sides. Translates of also tile the plane and determine how we color the plane using 7 colors.
It is easy to compute that each color does not have monochromatic segments of any length , where . Thus, if we proportionally shrink the configuration by a factor of, say, 2.1, we will get 7-coloring that has no monochromatic segments of unit length, which implies that .