In my previous posts I explained lower bounds for the Hadwiger-Nelson problem: we know that the chromatic number of the plane is at least 5 because there exist unit distance graphs which we know need at least 5 colors. Someday, perhaps someone will succeed in constructing an even bigger unit distance graph that requires 6 colors, and then we’ll know CNP .

But what about an upper bound? Can we say for sure that the CNP has to be smaller than some limit? Indeed, we can: we know that CNP . Today I want to explain how we can show that CNP ; in another post I’ll show the proof that CNP .

Proving an upper bound for the chromatic number of the plane is very different than proving a lower bound. A lower bound is all about showing that you can’t color the plane with a certain number of colors. An upper bound, on the other hand, is all about showing that you can. We know that CNP because there is a specific, valid way to color the plane using only seven colors! It might be possible to do it with fewer colors, using a very clever pattern, which is why is only an upper bound. But at least we know it can be done with .

Let’s start with something simpler. Imagine coloring the whole plane with a repeating pattern like this:

Can this be a valid coloring of the plane? (Of course, we already know it can’t because it only uses four colors, and CNP > 4; but let’s see if we can give a more direct argument why this is not valid). First of all, the squares can’t be too big: we don’t want any pair of points inside the same square to be 1 unit apart. This means the diagonal of each square has to be less than 1.

So if the diagonals of the squares are less than 1, the sides of the squares have to be less than . But the problem is that squares of the same color also have to be far enough apart so that no two points in same-colored squares are 1 unit apart. But in this scenario same-colored squares are separated by only one other square; if the sides of the squares is then they are too close.

This idea can be easily salvaged, however: we just need more colors!

Now we are using nine colors, with a repeating pattern instead of . Let’s see if we can make this work. Once again, the squares can’t be too big (lest two points inside the same square can be 1 unit apart) but same-color squares can’t be too close (lest two points in different same-color squares can be 1 unit apart). Call the side length of the squares. The first condition once again gives us . What about the second condition? The shortest distance between two same-colored squares is now , if you travel straight east-west or north-south. (You can confirm for yourself that any other line between same-colored squares is longer.) So we must have .

Can we pick a value of that makes and both true? Yes! Rearranging a bit, this just says . Since this gives us a valid range of values for ; any such value for gives us a valid -coloring of the plane.

Hence, it is possible to color the plane using 9 colors, such that no two points at distance 1 from each other have the same color! We don’t know if this is the best way to color the plane (in fact, it isn’t!), but at least we know it is a way. So this shows that CNP .

In my next post I’ll explain how we know that CNP : the proof is similar in spirit, but more complex (and, of course, more efficient) due to its use of hexagons instead of squares.